四种排序思想

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     }
复制代码

 

 

 

Tags: ,

IT技术

Comments (1) -

11/23/2019 6:15:51 PM #

administrator People's Republic of China

Add comment

  Country flag

biuquote
微笑得意调皮害羞酷大笑惊讶发呆喜欢可怜尴尬闭嘴噘嘴皱眉伤心抓狂呕吐坏笑漫骂发怒
Loading