本文共 6495 字,大约阅读时间需要 21 分钟。
1.冒泡排序
public class Test { public static void main(String[] args) { //待排数组 int[] arr = { 34,32,12,2,45,65,77,36}; //调用方法 sort(arr); //输出排序后的数组 System.out.println(Arrays.ToString(arr)); } //冒泡排序方法 public static void sort(int[] x) { for(int i = x.length; i > 0; i--) { for(int k = 0; k < i-1; k++) { if(x[k] > x[k+1]) { int c = x[k]; x[k] = x[k+1]; x[k+1] = c; } } } }}
2.快速排序
public class QuickSort { public static void main(String[] args) { //待排数组 int arr[] = new int[] { 6,1,2,7,9,3,4,5,10,8}; //调用方法 quickSort(arr,0,arr.length-1); //输出结果 System.out.println(Arrays.ToString(arr)); } public static void quickSort(int[] arr, int left, int right) { //进行判断,如果左边检索比右边检索大,不合法,return结束 if(left > right) { return; } //定义一个变量来保存基准数 int base = arr[left]; //定义变量i执行最左边 int i = left; //定义变量j执行最右边 int j = right; //当i和j不相等的时候,进行检索 while(i != j) { //j从右向左检索 while(arr[j] >= base && i < j) { j--; } //i从左向右检索 while(arr[i] <= base && i < j) { i++; } //当i和j都停下了,那么i和j的元素进行交换 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //当i与j相等 //将基准数和i位置的数进行交换 arr[left] = arr[i]; arr[i] = base; //排基准数左边的 quickSort(arr,left,i-1); //排基准数左边的 quickSort(arr,i+1,right); }}
3.选择排序
public class EasyChooseSort { //待排数组 public static int[] arr = new int[] { 8,65,25,41,6,42,9,10}; public static void main(String[] args) { //外层循环控制排序趟数 for(int i = 0; i < arr.length - 1; i++) { //最小值下标 int minIndex = i; //最小值 int min = arr[i]; //遍历数组查找最小值 for(int j = i+1;j < arr.length; j++) { //更新最小值 if(min > arr[j]) { min = arr[j]; minIndex = j; } } //交换 arr[minIndex] = arr[i]; arr[i] = min; //输出一趟排序结果 System.out.println(Arrays.toString(arr)); } System.out.println("最终结果"); //输出最终结果 System.out.println(Arrays.toString(arr)); }}
4.堆排序
public class HeapSort { public static void main(String[] args) { //待排数组 int[] arr = new int[] { 8,65,25,41,6,42,9,10}; //调用方法 heapSort(arr); //输出最终结果 System.out.println(Arrays.toString(arr)); } //创建堆的方法 public static void heapSort(int[] arr) { //从下方开始最小的一棵子树开始调整 for(int i = (arr.length-1-1)/2;i>=0;i--) { adjustHeap(arr,i,arr.length); } //堆顶尾交换 for(int i = arr.length-1;i>0;i--) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, i); } } //调整堆 public static void adjustHeap(int[] arr,int parent,int length) { //保存当前父节点的值 int temp = arr[parent]; //当前lChild为左孩子节点 int lChild = 2*parent + 1; while(lChild < length) { //右孩子节点 int rChild = lChild + 1; //当前lChild为左右孩子中最大的节点 if(rChild < length&&arr[rChild] > arr[lChild]) { lChild++; } //若父节点大于左右孩子节点,跳出循环 if(temp >= arr[lChild]) { break; } //将左右孩子中较大的节点的值赋给父节点 arr[parent] = arr[lChild]; //父节点=孩子节点,调整子树 parent = lChild; lChild = 2*lChild+1; } arr[parent]=temp; }}
5.插入排序
public class InsertSort { //待排数组 public static int[] arr = new int[] { 8,65,25,41,6,42,9,10}; public static void main(String[] args) { int j = 0; for(int i = 0;i < arr.length; i++) { //暂存要插入的数 int temp = arr[i]; //从后向前寻找插入位置 for(j = i-1;j >= 0;j--) { if(arr[j]>temp) { arr[j+1] = arr[j]; }else { break; } } //插入 arr[j+1] = temp; //输出每趟排序的结果 System.out.println(Arrays.toString(arr)); } //输出最终结果 System.out.println("最终结果"); System.out.println(Arrays.toString(arr)); }}
6.希尔排序
public class ShellSort { public static void main(String[] args) { //待排数组 int[] arr = new int[] { 8,65,25,41,6,42,9,10}; //调用方法 shellSort(arr); } public static void shellSort(int[] arr) { //定义一个用于进行交换的中间变量 int temp = 0; //开始进行希尔排序 ,初始步长为数组长度的一半,每一次步长减半 for(int gap = arr.length/2;gap > 0;gap /= 2) { for(int i = gap;i < arr.length; i++) { //遍历各组中的所有元素(共 gap组),步长gap for(int j = i-gap;j >= 0;j -= gap) { //如果当前元素大于 加上步长之后的那个元素,则进行交换 if(arr[j] > arr[j+gap]) { temp = arr[j]; arr[j] = arr[j+gap]; arr[j+gap] = temp; } } } } //最终结果 System.out.println(Arrays.toString(arr)); }}
7.归并排序
public class MergeSort { public static void main(String[] args) { //待排数组 int[] arr = new int[] { 8,65,25,41,6,42,9,10}; //调用方法 mergeSort(arr, 0, arr.length-1); //输出结果 System.out.println(Arrays.toString(arr)); } //拆分 public static void mergeSort(int[] arr,int low,int high) { //首先判断 low 和 high是否指向一个地方 if(low>=high) { return; } int mid = (low+high)/2; //递归拆分左边 mergeSort(arr, low, mid); //递归拆分右边 mergeSort(arr, mid+1, high); //合并 merge(arr, low, mid, high); } //合并 public static void merge(int[] arr,int low,int mid,int high) { int s1 = low; int s2 = mid+1; //定义临时数组 int[] temp = new int[high-low+1]; //定义临时数组的下标 int i = 0; //判断大小将数组放入到临时数组当中去 while(s1 <= mid && s2 <= high) { if(arr[s1] <= arr[s2]) { temp[i] = arr[s1]; i++; s1++; }else { temp[i] = arr[s2]; i++; s2++; } } //判断s1当中是否有数据,如果有将其全部拷贝到临时数组当中去 while(s1 <= mid) { temp[i] = arr[s1]; i++; s1++; } //判断s2当中是否有数据,如果有将其全部拷贝到临时数组当中去 while(s2 <= high) { temp[i] = arr[s2]; i++; s2++; } //将临时数组当中的数据放回原数组 for(int j = 0;j < temp.length;j++) { arr[j+low] = temp[j]; } }}
8.基数排序
public class RadixSort { public static void main(String[] args) { //待排数组 int[] arr = new int[] { 8,65,25,41,6,42,9,10}; //调用方法 sort(arr); //输出结果 System.out.println("最终结果:"+Arrays.toString(arr)); } public static void sort(int[] arr) { //得到数组中最大的数 int max = arr[0]; for(int i = 0;i < arr.length;i++) { if(arr[i] > max) { max = arr[i]; } } //得到最大的位数 int maxLength = (max+"").length(); //定义一个二维数组来表示我们这个桶 int[][] bucket = new int[10][arr.length]; //一维数组记录插入位置 int[] bucketCounts = new int[10]; //遍历计算每个数的个位 for(int k=0,n=1;k < maxLength;k++,n*=10) { for(int i = 0;i < arr.length;i++) { //取出每一个元素的个位 int element = arr[i]/n%10; //放入桶中,对应的bucketCounts记录+1 bucket[element][bucketCounts[element]] = arr[i]; bucketCounts[element]++; } int index = 0; //将桶中的数据放回数组,完成一趟排序 for(int i = 0;i < 10;i++) { //先判断桶内是否有数据 if(bucketCounts[i] != 0) { for(int j = 0;j < bucketCounts[i];j++) { arr[index++] = bucket[i][j]; } } //清空桶 bucketCounts[i] = 0; } //输出每趟排序的结果 System.out.println("第"+(k+1)+"趟"); System.out.println(Arrays.toString(arr)); } }}
转载地址:http://bsyki.baihongyu.com/