• 八大排序总是忘?快来这里~


    目录

    插入排序

    希尔排序

    选择排序

    冒泡排序

    堆排序

    快速排序(递归)

    快速排序(迭代)

    归并排序(递归)

    归并排序(迭代)

    计数排序



    注意:本文所有排序默认升序

    插入排序

    思路:

    •         首先从第一个元素开始可以被认为是已排好的元素
    •         向后遍历,从第二个元素开始,每次从后向前扫描
    •         遍历的元素若小于扫描到的元素,则交换,若没有,则将正在扫描的下一个元素正在遍历的元素交换
    •         重复以上操作,直到遍历完成

     代码如下:

    1. public void insertSort(int[] array){
    2. for(int i = 1; i < array.length; i++){
    3. int key = array[i];
    4. int j = i - 1;
    5. for(; j >= 0; j--){
    6. if(array[j] > key){
    7. array[j + 1] = array[j];
    8. }else{
    9. break;
    10. }
    11. }
    12. array[j + 1] = key;
    13. }
    14. }

    分析:

    •         时间复杂度:O(N^2) -> 数组为逆序; O(N)->数组顺序
    •         空间复杂度:O(1) 
    •         稳定性:稳定(稳定的可以修改为不稳定的,而不稳定的则不能修改为稳定的)
    •         思考:适合用于元素集合趋于稳定的(效率更高)

    希尔排序

     思路:

    •         用一个数gap(一般为元素总数除2)将待排序元素分成若干个组,组距为gap
    •         对每个组进行排序
    •         缩小gap的值(一般除2)
    •         继续重复以上操作
    •         直到gap值为1时,再重复以上操作即可
    •         本质是插入排序,但是会被分为若干组进行排序,逐渐趋向有序

    代码如下:

    1. public void shell3(int[] array, int gap){
    2. for(int i = gap ; i < array.length; i++){
    3. int key = array[i];
    4. int j = i - gap;
    5. for(; j >= 0; j -= gap){
    6. if(array[j] > key){
    7. array[j + gap] = array[j];
    8. }else{
    9. break;
    10. }
    11. }
    12. array[j + gap] = key;
    13. }
    14. }
    15. public void shellSort3(int[] array){
    16. int gap = array.length;
    17. while(gap > 1){
    18. gap /= 2;
    19. shell3(array, gap);
    20. }
    21. shell3(array, 1);
    22. }

    分析:

    •         时间复杂度:O(N^1.3 ~ N^1.4)
    •         空间复杂度:O(1)
    •         稳定性:不稳定
    •         思考:是对插入排序的优化,更适合无序的元素

    选择排序

     思路:

    •         从待排序的元素中遍历挑出一个最小值
    •         存放在起始位置
    •         再从这个起始位置向后遍历找出下一个最小值
    •         存放在上一个起始位置的下一个位置
    •         重复以上两步操作
    •         直到全部排完

    代码如下:

    1. public void chooseSort(int[] array){
    2. for(int i = 0; i < array.length; i++){
    3. for(int j = i + 1; j < array.length; j++){
    4. if(array[i] > array[j]){
    5. int tmp = array[i];
    6. array[i] = array[j];
    7. array[j] = tmp;
    8. }
    9. }
    10. }
    11. }

    分析:

    •      时间复杂度:O(N^2)  无论是有序还是无序,都是这么大
    •      空间复杂度:O(1)
    •      稳定性:不稳定
    •      思考:效率不高,少用

    冒泡排序

    思路: 

    •         从起始位置开始,两两向后比较,若第一个大于第二个,则交换
    •         用以上方法遍历(除了最后一个元素)完一遍后会将最大的元素排到最后
    •         重复以上方法(已经排到后面的元素不用进行比较了)
    •         直到没有要比较的元素后,停止

    代码如下:

    1. public void bubbleSort(int[] array){
    2. for(int i = 0; i < array.length - 1; i++){
    3. for(int j = 0; j < array.length - i - 1; j++){
    4. if(array[j] > array[j + 1]){
    5. int tmp = array[j];
    6. array[j] = array[j + 1];
    7. array[j + 1] = tmp;
    8. }
    9. }
    10. }
    11. }
    1. 对于冒泡排序,若已排好序,在这样排,实在浪费时间
    2. 可以建立一个flag判断,是否有进行排序操作,优化如下:
    1. public void bubbleSort(int[] array){
    2. for(int i = 0; i < array.length - 1; i++){
    3. boolean flag = false;
    4. for(int j = 0; j < array.length - i - 1; j++){
    5. if(array[j] > array[j + 1]){
    6. int tmp = array[j];
    7. array[j] = array[j + 1];
    8. array[j + 1] = tmp;
    9. flag = true;
    10. }
    11. }
    12. if(!flag){
    13. break;
    14. }
    15. }
    16. }

    分析:

    •         时间复杂度:O(N^2),优化后的代码在有序的情况下时间复杂度为O(N)
    •         空间复杂度:O(1)
    •         稳定性:稳定
    •         思考:一种新手最容易上手的排序方式

    堆排序

    思路: 

    •         用待排序元素建立一个大根堆(降序建立小根堆)
    •         交换下标为0的位置与最后一个元素的结点
    •         继续向下调整为大根堆
    •         再次交换时,交换下标0与最后一个元素的上一个元素
    •         重复以上操作
    •        直到下标为0位置与0位置交换时停止

    代码如下:

    1. //堆排序
    2. public void heapSort(int[] array){
    3. createBigHeap(array);
    4. int end = array.length - 1;
    5. while(end > 0){
    6. //这里不需要在判断大小,因为大根堆最上面本来就是最大的,直接交换即可
    7. swap(array, end, 0);
    8. adjustmentDown(array, 0, end);
    9. end--;
    10. }
    11. }
    12. //创建大根堆
    13. public void createBigHeap(int[] array){
    14. int len = array.length;
    15. for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
    16. adjustmentDown(array, parent, len);
    17. }
    18. }
    19. //向下调整
    20. public void adjustmentDown(int[] array, int parent, int len){
    21. int child = parent * 2 + 1;
    22. while(child < len){
    23. //必须保证要有右孩子
    24. if(child + 1 < len && array[child] < array[child + 1]){
    25. child++;
    26. }
    27. if(array[parent] < array[child]){
    28. swap(array, parent, child);
    29. parent = child;
    30. child = parent * 2 + 1;
    31. }
    32. else{
    33. //如果根节点大于孩子结点后面就没必要比较了
    34. break;
    35. }
    36. }
    37. }
    38. //交换
    39. public void swap(int[] array, int i, int j){
    40. int tmp = array[i];
    41. array[i] = array[j];
    42. array[j] = tmp;
    43. }

    分析:

    •         时间复杂度:O(N * logN)
    •         空间复杂度:O(1)
    •         稳定性:不稳定
    •         思考:效率高了很多

    快速排序(递归)

     思路:(递归思路)

    •         从元素集合中挑出一个数(“基准”)
    •         将小于基准的数放到基准前面,大于基准的数放到基准后面,分完之后将基准放到分基准时停止的位置即可
    • 递归将大于基准的子集合和小于基准的子集合用上述方法继续分配

    如下代码:(递归,未优化)

    1. //快速排序
    2. //找基准
    3. public int fundPivot(int[] array,int start, int end){
    4. int key = array[start];
    5. while(start < end){
    6. //取等于号方式头尾元素相等造成死循环
    7. //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
    8. //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
    9. while(start < end && key <= array[end]){
    10. end--;
    11. }
    12. array[start] = array[end];
    13. while(start < end && array[start] <= key){
    14. start++;
    15. }
    16. array[end] = array[start];
    17. }
    18. //将基准放入停止时的位置
    19. array[start] = key;
    20. return start;
    21. }
    22. //分组递归
    23. public void quick(int[] array, int left, int right){
    24. if(left >= right){
    25. return;
    26. }
    27. int pivot = fundPivot(array, left, right);
    28. quick(array, left, pivot - 1);
    29. quick(array, pivot + 1, right);
    30. }
    31. //充当个接口,同一传入的值为数组
    32. public void quickSort(int[] array){
    33. quick(array, 0, array.length - 1);
    34. }

            ​​​​​​存在的问题:当给的数据是有序(升序或降序)的,这时的快排时间复杂度会达到O(N^2),仅在元素集合是杂乱无章的情况下时间复杂度接近O(N*logN)为了解决这个问题,引入了三数取中法;

            三数取中法思路:对待排序元素给定三个下标,第一个下标left指向最左边的元素,第二个下标right指向最右边的元素,第三个下标mid指向指向中间值-> (left + right) / 2,得到这三个下标后再求出这三个下标所指向的数据的中位数作为“基准”,这样找出的基准更可以将元素集合均分(基本就是二分),在数据有序情况下大大降低时间复杂度,趋近O(N*logN)。

    如下代码:(第一步优化)

    1. //快速排序
    2. //找基准
    3. public int fundPivot(int[] array,int start, int end){
    4. int key = array[start];
    5. while(start < end){
    6. //取等于号方式头尾元素相等造成死循环
    7. //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
    8. //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
    9. while(start < end && key <= array[end]){
    10. end--;
    11. }
    12. array[start] = array[end];
    13. while(start < end && array[start] <= key){
    14. start++;
    15. }
    16. array[end] = array[start];
    17. }
    18. //将基准放入停止时的位置
    19. array[start] = key;
    20. return start;
    21. }
    22. //寻找中间值交换
    23. public int funMidIndex(int[] array, int left, int right){
    24. int mid = (left + right) / 2;
    25. if(array[left] < array[right]){
    26. if(array[mid] < array[left]){
    27. return left;
    28. }else if(array[right] < array[mid]){
    29. return right;
    30. }else{
    31. return mid;
    32. }
    33. }else{
    34. if(array[left] < array[mid]){
    35. return left;
    36. }else if(array[mid] < array[right]){
    37. return right;
    38. }else{
    39. return mid;
    40. }
    41. }
    42. }
    43. //分组递归
    44. public void quick(int[] array, int left, int right){
    45. if(left >= right){
    46. return;
    47. }
    48. int midIndex = funMidIndex(array, left, right);
    49. swap(array, left, midIndex);
    50. int pivot = fundPivot(array, left, right);
    51. quick(array, left, pivot - 1);
    52. quick(array, pivot + 1, right);
    53. }
    54. //充当个接口,同一传入的值为数组
    55. public void quickSort(int[] array){
    56. quick(array, 0, array.length - 1);
    57. }

    存在问题:递归的层次太多,元素集合过大可能导致栈溢出;

    解决办法:即使三数取中法一定程度上也减少了递归的深度,但是在庞大的数据下不足以支撑,减少递归层次;想象以下,递归最后一层实现了多少次递归呢?是2^(n - 1),而整个快速排序总共才递归2^n - 1,相当于最后一层递归就占了整个快排递归数量的一半多,不难想到,递归到结尾的时候,完全没有必要再递归下去,因为数据已经趋于有序,所以这个时候就可以用到插入排序,大大减少递归次数,防止栈溢出。

    代码如下:(递归层次的优化)

    1. //快速排序
    2. //插入排序
    3. public void insertSort(int[] array, int start, int end){
    4. for(int i = start + 1; i <= end; i++){
    5. int key = array[i];
    6. int j = i - 1;
    7. for(; j >= 0; j--){
    8. if(array[j] > key){
    9. array[j + 1] = array[j];
    10. }else{
    11. break;
    12. }
    13. }
    14. array[j + 1] = key;
    15. }
    16. }
    17. //找基准
    18. public int fundPivot(int[] array,int start, int end){
    19. int key = array[start];
    20. while(start < end){
    21. //取等于号方式头尾元素相等造成死循环
    22. //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
    23. //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
    24. while(start < end && key <= array[end]){
    25. end--;
    26. }
    27. array[start] = array[end];
    28. while(start < end && array[start] <= key){
    29. start++;
    30. }
    31. array[end] = array[start];
    32. }
    33. //将基准放入停止时的位置
    34. array[start] = key;
    35. return start;
    36. }
    37. //寻找中间值交换
    38. public int funMidIndex(int[] array, int left, int right){
    39. int mid = (left + right) / 2;
    40. if(array[left] < array[right]){
    41. if(array[mid] < array[left]){
    42. return left;
    43. }else if(array[right] < array[mid]){
    44. return right;
    45. }else{
    46. return mid;
    47. }
    48. }else{
    49. if(array[left] < array[mid]){
    50. return left;
    51. }else if(array[mid] < array[right]){
    52. return right;
    53. }else{
    54. return mid;
    55. }
    56. }
    57. }
    58. //分组递归
    59. public void quick(int[] array, int left, int right){
    60. if(left >= right){
    61. return;
    62. }
    63. //假设数据非常大
    64. //这里相当于减少了7层递归
    65. if(right - left + 1 <= 7){
    66. insertSort(array, left, right);
    67. }
    68. int midIndex = funMidIndex(array, left, right);
    69. swap(array, left, midIndex);
    70. int pivot = fundPivot(array, left, right);
    71. quick(array, left, pivot - 1);
    72. quick(array, pivot + 1, right);
    73. }
    74. //充当个接口,同一传入的值为数组
    75. public void quickSort(int[] array){
    76. quick(array, 0, array.length - 1);
    77. }

    分析:(最后一次优化)

    •         时间复杂度:O(N*logN)
    •         空间复杂度:O(logN)
    •         稳定性:不稳定
    •         思考:综合性能较高,适用于多种场合

    快速排序(迭代)

    思路:大致思路与递归相似,很多重复的东西下面就不细讲了(如三数取中法...)

    •         建立一个栈,用来存放待排序区间的左右边界
    •         可以通过三数去中法优化,然后找到“基准”
    •         在基准的左边的元素个数不小于1的时候(否则视为有序),将基准左边区间的左右边界所指向的下标压入栈中,基准右边区间也是同样的操作
    •         在栈不为空的前提下,弹出栈中两个元素,继续重复以上操作即可

    代码如下:(经三数取中法优化

    1. //非递归快排
    2. //寻找中间值交换
    3. public int funMidIndex(int[] array, int left, int right){
    4. int mid = (left + right) / 2;
    5. if(array[left] < array[right]){
    6. if(array[mid] < array[left]){
    7. return left;
    8. }else if(array[right] < array[mid]){
    9. return right;
    10. }else{
    11. return mid;
    12. }
    13. }else{
    14. if(array[left] < array[mid]){
    15. return left;
    16. }else if(array[mid] < array[right]){
    17. return right;
    18. }else{
    19. return mid;
    20. }
    21. }
    22. }
    23. //找基准
    24. public int fundPivot(int[] array,int start, int end){
    25. int key = array[start];
    26. while(start < end){
    27. //取等于号方式头尾元素相等造成死循环
    28. //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
    29. //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
    30. while(start < end && key <= array[end]){
    31. end--;
    32. }
    33. array[start] = array[end];
    34. while(start < end && array[start] <= key){
    35. start++;
    36. }
    37. array[end] = array[start];
    38. }
    39. //将基准放入停止时的位置
    40. array[start] = key;
    41. return start;
    42. }
    43. public void quickSort(int[] array){
    44. int left = 0;
    45. int right = array.length - 1;
    46. Stack stack = new Stack<>();
    47. //三数取中法优化
    48. int midIndex = funMidIndex(array, left, right);
    49. swap(array, left, midIndex);
    50. int pivot = fundPivot(array, left, right);
    51. //若基准左边或右边的数据不超过一个,则将下标压入栈,否则就是有序
    52. if(left + 1 < pivot){
    53. stack.push(left);
    54. stack.push(pivot - 1);
    55. }
    56. if(right - 1 > pivot){
    57. stack.push(pivot + 1);
    58. stack.push(right);
    59. }
    60. //只要栈不为空,就每次弹出栈顶的两个元素作为左右边界,继续进行如上操作
    61. while(!stack.isEmpty()){
    62. right = stack.pop();
    63. left = stack.pop();
    64. midIndex = funMidIndex(array, left, right);
    65. swap(array, left, midIndex);
    66. pivot = fundPivot(array, left, right);
    67. if(left + 1 < pivot){
    68. stack.push(left);
    69. stack.push(pivot - 1);
    70. }
    71. if(right - 1 > pivot){
    72. stack.push(pivot + 1);
    73. stack.push(right);
    74. }
    75. }
    76. }

    归并排序(递归)

     思路:

    •         找到元素集合的中间下标,分成左段和右端(类似二叉树递归)
    •         通过递归再继续将其左右段继续分为更小的子段
    •         使每个子端有序
    •         将分成的两路字段最后合并成一个新的有序的元素集合(具体实现过程看: 归并排序的迭代版本,下面有)

    代码如下:

    1. //归并排序
    2. private void mergeFunc(int[] array, int left, int right){
    3. if(left == right){
    4. return;
    5. }
    6. int mid = (left + right) / 2;
    7. //分解左边(包含mid下标元素)
    8. mergeFunc(array, left, mid);
    9. //分解右边
    10. mergeFunc(array, mid + 1, right);
    11. //合并
    12. merge(array, left, right, mid);
    13. }
    14. //合并
    15. private void merge(int[] array, int start, int end, int midIndex){
    16. int[] tmpArr = new int[end - start + 1];
    17. //tmpArr数组的零下标
    18. int k = 0;
    19. int s1 = start;
    20. int s2 = midIndex + 1;
    21. //两个同时比较
    22. while(s1 <= midIndex && s2 <= end){
    23. //这里因为是<=所以才是一个稳定的排序
    24. if(array[s1] <= array[s2]){
    25. tmpArr[k++] = array[s1++];
    26. }else{
    27. tmpArr[k++] = array[s2++];
    28. }
    29. }
    30. //若比较完后,还剩余一方未比较完,直接将剩下的一方拼上
    31. while(s1 <= midIndex){
    32. tmpArr[k++] = array[s1++];
    33. }
    34. while(s2 <= end){
    35. tmpArr[k++] = array[s2++];
    36. }
    37. //把排好序的数字从start处开始拷贝回原数组
    38. for(int i = 0; i < k; i++){
    39. array[i + start] = tmpArr[i];
    40. }
    41. }
    42. public void mergeSort(int[] array){
    43. mergeFunc(array, 0, array.length - 1);
    44. }

    分析:

    •         时间复杂度:严格意义上(不论是否有序)的O(N * logN)
    •         空间复杂度:O(N)
    •         稳定性:稳定
    •         思考:空间复杂度大,不考虑空间的情况下适用

    归并排序(迭代)

    思路:(一定要注意指针下标的合理性)

    1.先将整个数据其分成一个数据为一组,共分为两组,如下图(红为一组,蓝为一组)

     2.两组之间相互比较,并排序,如下图

    3.再将组距放大一倍,相当于一组两个元素,如下图

     4.给定指针如下图(一组一个元素的时候就有指针,当时表示用处不大,此时标注方便理解)

     5.接下来就是合并两个有序的数组 :创建一个大小可以容纳所有元素的数组,先比较s1,s2谁小,将小的放入新数组,如下图

    6.继续重复以上3~5操作,直到s1 > e1或s2 > e2时停止,若这两组,有一方先停止,就将剩下的一方直接从后加到数组中去 ,再继续扩到组距(直到大于数组总大小为止)...

     代码如下:

    1. //合并
    2. private void merge(int[] array, int start, int end, int midIndex){
    3. int[] tmpArr = new int[end - start + 1];
    4. //tmpArr数组的零下标
    5. int k = 0;
    6. int s1 = start;
    7. int s2 = midIndex + 1;
    8. //两个同时比较
    9. while(s1 <= midIndex && s2 <= end){
    10. //这里因为是<=所以才是一个稳定的排序
    11. if(array[s1] <= array[s2]){
    12. tmpArr[k++] = array[s1++];
    13. }else{
    14. tmpArr[k++] = array[s2++];
    15. }
    16. }
    17. //若比较完后,还剩余一方未比较完,直接将剩下的一方拼上
    18. while(s1 <= midIndex){
    19. tmpArr[k++] = array[s1++];
    20. }
    21. while(s2 <= end){
    22. tmpArr[k++] = array[s2++];
    23. }
    24. //把排好序的数字从start处开始拷贝回原数组
    25. for(int i = 0; i < k; i++){
    26. array[i + start] = tmpArr[i];
    27. }
    28. }
    29. public void mergeSort(int[] array){
    30. int gap = 1;
    31. while(gap < array.length){
    32. // i+= gap*2 是为了保证s1可以跳过e2、s2、e2到下一个待排序位置
    33. for(int i = 0; i < array.length; i += gap * 2){
    34. //首先能进循环i一定合法
    35. int s1 = i;
    36. int e1 = i + gap - 1;
    37. //注意保证指针不会越界!一旦越界采取强制措施,如下
    38. if(e1 > array.length - 1){
    39. e1 = array.length - 1;
    40. }
    41. int s2 = e1 + 1;
    42. if(s2 > array.length - 1){
    43. s2 = array.length - 1;
    44. }
    45. int e2 = s2 + gap - 1;
    46. if(e2 > array.length - 1){
    47. e2 = array.length - 1;
    48. }
    49. merge(array, s1, e2, e1);
    50. }
    51. gap *= 2;
    52. }
    53. }

    分析:

    •         时间复杂度:严格意义上(不论是否有序)的O(N * logN)
    •         空间复杂度:O(N)
    •         稳定性:稳定
    •         思考:空间复杂度大,不考虑空间的情况下适用

    计数排序

     思路:

    •         通过待排序的元素集合找出最大值与最小值来确定计数数组的大小
    •         通过遍历待排序数组,统计相同元素出现的次数(具体如上动态图)
    •         遍历计数器数组,将统计出的结果回归到原序列中

    代码如下:

    1. public void countSort(int[] array){
    2. int maxIndex = array[0];
    3. int minIndex = array[0];
    4. for(int i = 0; i < array.length; i++){
    5. if(array[i] > maxIndex){
    6. maxIndex = array[i];
    7. }
    8. if(array[i] < minIndex){
    9. minIndex = array[i];
    10. }
    11. }
    12. //假设最大值66,最小值60,则有66 - 60 = 6个数据,而60~66实际上有7个数据,所以加一
    13. int[] countArr = new int[maxIndex - minIndex + 1];
    14. //开始计数
    15. for(int i = 0; i < array.length; i++){
    16. countArr[array[i] - minIndex]++;
    17. }
    18. //写入原数组
    19. int index = 0;//array的下标
    20. for(int i = 0; i < countArr.length; i++){
    21. while(countArr[i] != 0){
    22. array[index] = i + minIndex;
    23. countArr[i]--;
    24. index++;
    25. }
    26. }
    27. }

    分析:

    •         时间复杂度:O(N + 数据范围)
    •         空间复杂度:O(数据范围)
    •         稳定性:很多资料上说是稳定的(博主这个代码是不稳定的😂)
    •         思考:适合给定范围的数据进行排序,并且不需要比较元素之间的大小

  • 相关阅读:
    基于 Laravel 封装参数校验
    振弦采集模块复位( 重启)及恢复出厂设置
    数据增强Mixup原理与代码解读
    【工具知识】——类图的快速入门
    conda: error: argument COMMAND: invalid choice: ‘activate‘
    Win11策略服务被禁用怎么办?Win11策略服务被禁用的解决方法
    buuctf-[WUSTCTF2020]朴实无华
    01-初识HTML
    【前端面试常问】MVC与MVVM
    打开游戏提示xapofx1_5.dll丢失如何修复?xapofx1_5.dll缺失的修复教程分享
  • 原文地址:https://blog.csdn.net/CYK_byte/article/details/126232684