posted at 2019.10.25 16:06 by 风信子
1.冒泡排序：
思想：比较相邻元素，违反排序顺序则交换，每次冒出一个最大值，直到所有相对的最大值冒出，完成排序。
最基本的排序。
复杂度：最坏：O(n*n)；最好：O(n)；O(n*n)。
1 private static void bubblesort(int[] arr) { 2 for (int i = 0; i < arr.length - 1; i++) { // n-1趟
3 for (int j = 0; j < arr.length - 1 - i; j++) { // 每趟比n-1-i次
4 if (arr[j] > arr[j + 1]) { 5 int temp = arr[j + 1]; // 交换
6 arr[j + 1] = arr[j]; 7 arr[j] = temp; 8 } 9 } 10 } 11 }
2.快速排序：
思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
复杂度：最坏：O(n*n)；最好：O(n*logn)；平均：O(n*logn)。
1 private static void quickSort(int[] arr, int start, int end) { 2 if (start > end)// 出口
3 return; 4
5 int stard = arr[start];// 将数组的首值设为参照值
6
7 int low = start;// 记录需要排序的下标
8 int high = end; 9
10 while (low < high) {// 循环找出比参照值大和小的数
11 while (low < high && stard <= arr[high]) {// 右边的数比参照大
12 high--; 13 } 14 arr[low] = arr[high];// 此时跳出内层循环遇到arr[high]<stard；用右边的数替换左边的数
15 while (low < high && stard >= arr[low]) {// 左边的数比参照小
16 low++; 17 } 18 arr[high] = arr[low];// 此时arr[low]>atard
19 } 20 arr[low] = stard;// 将参照赋给low位置的数
21 quickSort(arr, start, low - 1);// 处理所有的小的数字
22 quickSort(arr, low + 1, end);// 处理所有的大的数字
23
24 }
3.简单插排：
思想：假设待插入元素之前的元素已经是排序完成的，则每一步将一个待排序的元素，按其值的大小插入前面已经排序的序列中适当位置上，直到全部插入完为止。
其中插入具体是指：对于待插入元素temp,如果i位置还不是插入合适的位置，则把i-1位置的元素填到i位置，直到找到合适的位置，或者遍历到0位置，将temp填在i位置。
复杂度：最坏：O(n*n)；最好：O(n*n)；平均：O(n*n)。
1 private static void insertSort(int[] arr) { 2 for (int i = 1; i < arr.length; i++) {// 从第二个元素开始遍历
3 if (arr[i] < arr[i - 1]) { // 遇到当前元素比前一个元素小的情况
4 int temp = arr[i]; // 保存当前元素
5 int j;//用于遍历前面所有的情况
6 for (j = i - 1; j >= 0 && arr[j] > temp; j--) { // 往前遍历，找到合适的插入位置
7 arr[j + 1] = arr[j]; 8 } 9 arr[j + 1] = temp; // 将保存的值存入，即插入到合适的位置，完成排序
10 } 11 } 12 }
4.希尔排序：又称缩小增量排序
思想：按除2递减的步长将序列分组，每组使用直接插排，直到每组都进行插排后完成排序。
复杂度：最坏：O(n*logn*logn)；最好：O(n)；平均：取决于间隔序列。
1 private static void shellSort(int[] arr) { 2 // 遍历步长
3 for (int step = arr.length / 2; step > 0; step /= 2) { 4 // 每次进行直接插入排序
5 for (int i = step; i < arr.length; i += step) { 6 if (arr[i] < arr[i - step]) { 7 int temp = arr[i]; 8 int j; 9 for (j = i - step; j >= 0 && arr[j] > temp; j -= step) { 10 arr[j + step] = arr[j]; 11 } 12 arr[j + step] = temp; 13 } 14 } 15 } 16 }
69564a01-481d-4799-beda-985da623b161|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: 数据, 代码
IT技术
