【数据结构】七种常见排序算法详解（直接插入、希尔、选择、冒泡、快速，归并、堆排序）

悠悠 2022-05-21 22:49 296阅读 0赞

一、什么是排序？

**【1】排序：**就是将一组杂乱无章的数据按照一定的规律(升序或降序)组织起来。
**数据表：**待排序数据元素的有限集合。
排序码：通常数据元素有多个属性域，其中有一个属性域可用来区分元素，作为排序依据，该域 即为排序码。
如果在数据表中各个元素的排序码互不相同，这种排序码称为主排序码。

  • 按照主排序码进行排序，排序的结果是唯一的。
  • 按照次排序码进行排序，排序的结果可能是不唯一的。

二、排序分类

这里写图片描述

三、预备知识

简单的说就是将一组数中相等的数经过某种排序算法后，依然能够保持它在排序之前的相对次序，就称该方法是稳定的，反之为稳定；
（1）稳定排序的示意图如下：
这里写图片描述
（2）内排序和外排序
在排序过程中，所有需要排序的数据都一次性加载到内存中，并在内存中调整他们的顺序，称之为内排序；如果数据较大，只有部分被调入到内存，并借助内存调整在内存外中存放顺序，成为外排序；

（3）时间复杂度和空间复杂度
所谓的算法时间复杂度，就是指执行该算法所需要的计算工作量，空间复杂度就是执行该算法所需要的内存空间。

四、七种算法详解

###【1】直接插入排序
（1）算法思想
在待排序的一组数中，假设前面n-1(n>=2)个数已经排好序了，现在要将第n个数插入到前面的n-1个有序数中，使得这n个数是排好序的，如此反复循环，直到全部排好序；

（2）算法性质

  • 直接排序是稳定的;
  • 算法的时间复杂度为O(n^2);
  • 适用于量小、接近有序的数据

（3）算法示意图
这里写图片描述

（4）程序代码

  1. #include<iostream>
  2. using namespace std;
  4. template<typename T>
  5. void Insert_sort(T *array,int len)//排序函数
  6. {
  7.     int key;
  8.     int end;
  9.     for(int i = 1; i < len ;i++)
  10.     {
  11.         key = array[i];
  12.         for(end = i-1; (end>=0) && array[end] >key ;end--)
  13.         {
  14.             array[end+1] = array[end];
  15.         }
  17.         array[end+1] = key;
  18.     }
  19. }
  20. template<typename T>
  21. void Print( T array,int len )//打印函数
  22. {
  23.     for(int i = 0;i <len ;i++)
  24.     {
  25.         cout<<array[i]<<endl;
  26.     }
  27. }
  29. int main()
  30. {
  31.     int array[10] = {3,4,2,1,7,6,8,9,0,5};
  32.     int len = sizeof(array)/sizeof(array[0]);
  33.     Insert_sort(array, len);
  34.     Print(array,len );
  35.     return 0;
  36. }

（5）结果展示
这里写图片描述

###【2】希尔排序
（1）算法思想
在直接排序中，使有序序列只增加一个节点，并且对插入下一个数没有任何关联，所以希尔排序就是对直接排序的一种改进。希尔算法是将一组数按某个增量gap分为若干个组，每组中的下标相差gap，对每组中在进行排序，当gap=1时，整个要排序的数就被分成一组，排序完成。

（2）算法性质

  • 直接排序是不稳定的;
  • 算法的时间复杂度为O(n^1.3);

  • 适用于量大、接近有序的数据
    （3）算法示意图
    这里写图片描述
    （4）程序代码

    include

    using namespace std;

    template
    void Shell_Sort(T *array,int len)
    {

    1. int gap = len ;
    2. int key;
    3. int end;
    4. do
    5. {
    6.     gap = gap/3 +1;
    7.     gap =1;
    8.     for(int i = gap; i<len; i+=gap)
    9.     {
    10.         key = array[i];
    12.         for(end = i-gap; (end >= 0)&&(array[end]>key);end-=gap )
    13.         {
    14.             array[end+gap] = array[end];
    15.         }
    16.         array[end+gap] = key;
    17.     }
    18. }while(gap>1);

    }

    template
    void Print( T array,int len )
    {

    1. for(int i = 0;i <len ;i++)
    2. {
    3.     cout<<array[i]<<endl;
    4. }

    }

    int main()
    {

    1. int array[10] = {3,4,2,1,7,6,8,9,0,5};
    2. //char array[] = "sacbfdeghjioznm";
    3. int len = sizeof(array)/sizeof(array[0]);
    5. Shell_Sort(array, len);
    6. Print(array,len );
    8. return 0;

    }

(5)结果展示
这里写图片描述

###【3】选择排序
（1）算法思想
在待排序的一组数中，按住一个数不动，将其与剩下的每一个数比较，如果满足条件，则交换，否则继续比较如此循环上述步骤，直至每个数都排好序；

（2）算法示意图
这里写图片描述
（3）程序代码

  1. #include<iostream>
  2. using namespace std;
  3. template<typename T>
  4. void printArray01(T array[], int len)
  5. {
  6.     int i = 0;
  7.     for(i=0; i<len; i++)
  8.     {
  9.         cout<<array[i]<<endl;
  10.     }
  11. }
  12. template<typename T>
  13. void myswap(T array[],int i,int j)
  14. {
  15.                 int tmp = array[i];
  16.                 array[i] = array[j];
  17.                 array[j] = tmp;
  18. }
  19. template<typename T>
  20. void select_sort(T array[],int size)
  21. {
  22.     int min;
  23.     for(int i = 0; i<size;i++)
  24.     {
  25.         min = i;
  26.         for(int j= i+1;j<size;j++)
  27.         {
  28.             if(array[j] <array[min])
  29.             {
  30.                 min = j;
  31.             }
  32.         }
  33.         myswap(array,i,min);
  34.     }
  35. }
  37. int main()
  38. {
  39.     //int buf[10]={2,3,4,1,6,5,7,8,0,9};
  40.     char buf[] = "sacbfdeghjioznm";
  41.     int len = sizeof(buf)/sizeof(buf[0]);
  43.     select_sort(buf,len);
  45.     printArray01(buf,len);
  46.     return 0;
  47. }

（4）结果展示
这里写图片描述
###【4】冒泡排序
（1）算法思想
冒泡排序是较为常用的方法，它是相邻元素之间进行比较，交换，一趟排序下来，找到该组数据中最大（最小的元素），接下来，再在剩下的数中比较，找次大元素，直至所有的数都排好序为止；
（2）算法示意图
这里写图片描述

（3）程序代码

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  5. template<typename T>
  6. void bubble_sort(T *array, int len)
  7. {
  8.     int tmp;
  9.     int exchange = 1;
  10.     for(int i = 0; (i<len)&& exchange ;i++)
  11.     {
  12.         exchange  = 0;
  13.         for(int j = len -1;j > 0 ;j --)
  14.         {
  15.             if(array[j]<array[j-1])
  16.             {
  17.                 tmp = array[j];
  18.                 array[j] = array[j-1];
  19.                 array[j-1] = tmp;
  20.                 exchange = 1;
  21.             }
  22.         }
  23.     }
  24. }
  25. template<typename T>
  26. void Print( T array,int len )
  27. {
  28.     for(int i = 0;i <len ;i++)
  29.     {
  30.         cout<<array[i]<<endl;
  31.     }
  32. }
  34. int main()
  35. {
  36.     //int array[10] = {3,4,2,1,7,6,8,9,0,5};
  37.     char array[] = "sacbfdeghjioznm";
  38.     int len = sizeof(array)/sizeof(array[0]);
  40.     bubble_sort(array, len);
  42.     Print(array,len );
  44.     return 0;
  45. }

（4）结果展示
这里写图片描述

###【5】快速排序
（1）算法思想
在待排序的一组数中，随机找一个数，将它作为枢轴，然后，将该组数据分为两部分，一部分比它大，另一部分比它小，如果要求该组数据是升序排列，那么，就将比它小的数放在该数的左边，把比它大的数放在他的后面，循环往复。。。
（2）算法示意图
这里写图片描述
（3）程序代码

  1. #include<iostream>
  2. using namespace std;
  3. void Swap66(int *array,int low , int high)
  4. {
  5.     int tmp= array[low];
  6.     array[low] =array[high];
  7.     array[high] = tmp;
  8. }
  10. int partion(int *array, int low,  int high)
  11. {
  12.     int qv  = array[low];
  13.     while(low < high)
  14.     {
  15.         while((low<high) && (qv < array[high]))
  16.         {
  17.             high--;
  18.         }
  20.         Swap66(array, low ,high);
  21.         while( (low<high)&& (qv>=array[low] ) )
  22.         {
  23.             low++;
  24.         }
  25.         Swap66(array, low ,high);
  26.     }
  27.     return low;
  28. }
  30. void _sort(int* array,int low,int high)
  31. {
  32.     if(low<high)//注意条件必须加！！！！！！！！！！
  33.     {
  34.         int qv = partion(array, low, high);
  35.         _sort(array, low , qv-1 );
  36.         _sort(array, qv+1, high);
  37.     }
  38. }
  39. void Quick_sort(int* array,int len)
  40. {
  41.      _sort(array,0,len-1);
  42. }
  44. void Print(int *array ,int len)
  45. {
  46.     for(int i = 0;i <len;i++)
  47.     {
  48.         cout<<array[i]<<endl;
  49.     }
  50. }
  52. int main()
  53. {
  54.     int array[]={6,7,5,4,3,9,1,2,0,8};
  55.     //char array[]="dcbazyxqpo";
  56.     int len =sizeof(array)/sizeof(array[0]);
  58.     Quick_sort(array,len);
  59.     Print(array,len);
  60.     return 0;
  61. }

（4）结果展示
这里写图片描述
###【6】归并排序
（1）算法思想
在待排序的数据中，先将其划分为若干个有序的小序列，再将这每个小序列合并成大序列，以此往复；

（2）算法示意图
这里写图片描述
（3）程序代码

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. void printArray06(int array[], int len)
  5. {
  6.     int i = 0;
  7.     for(i=0; i<len; i++)
  8.     {
  9.         printf("%d ", array[i]);
  10.     }
  11.     printf("\n");
  12. }
  14. void swap6(int array[], int i, int j)
  15. {
  16.     int temp = array[i];
  17.     array[i] = array[j];
  18.     array[j] = temp;
  19. }
  21. void Merge(int src[], int des[], int low, int mid, int high)
  22. {
  23.     int i = low;
  24.     int j = mid + 1;
  25.     int k = low;
  27.     while( (i <= mid) && (j <= high) ) //将小的放到目的地中
  28.     {
  29.         if( src[i] < src[j] )
  30.         {
  31.             des[k++] = src[i++];
  32.         }
  33.         else
  34.         {
  35.             des[k++] = src[j++];
  36.         }
  37.     }
  39.     while( i <= mid )  //若还剩几个尾部元素
  40.     {
  41.         des[k++] = src[i++];
  42.     }
  44.     while( j <= high ) //若还剩几个尾部元素
  45.     {
  46.         des[k++] = src[j++];
  47.     }
  48. }
  50. //每次分为两路 当只剩下一个元素时，就不需要在划分
  51. void MSort(int src[], int des[], int low, int high, int max)
  52. {
  53.     if( low == high ) //只有一个元素，不需要归并，结果赋给des[low]
  54.     {
  55.         des[low] = src[low]; 
  56.     }
  57.     else //如果多个元素，进行两路划分
  58.     {
  59.         int mid = (low + high) / 2;
  60.         int* space = (int*)malloc(sizeof(int) * max);
  62.         //递归进行两路，两路的划分 
  63.         //当剩下一个元素的时，递归划分结束，然后开始merge归并操作
  64.         if( space != NULL )
  65.         {
  66.             MSort(src, space, low, mid, max); 
  67.             MSort(src, space, mid+1, high, max);
  68.             Merge(space, des, low, mid, high); //调用归并函数进行归并
  69.         }
  71.         free(space);
  72.     }
  73. }
  75. void MergeSort(int array[], int len) // O(n*logn)
  76. {
  77.     MSort(array, array, 0, len-1, len);
  78. }
  80. int main()
  81. {
  82.     int array[] = {21, 25, 49, 25, 16, 8};
  83.     int len = sizeof(array) / sizeof(*array); 
  84.     printArray06(array, len);
  85.     MergeSort(array, len);
  86.     printArray06(array, len);
  87.     return 0;
  88. }

（4）结果展示
这里写图片描述

###【7】堆排序
（1）算法思想
顾名思义，堆排序是利用大堆小堆来进行排序，使用向上调整以及向下调整的方法进行排序；分为两个大的部分：
（1）、建堆
（2）、排序
（2）程序代码

  1. #include<iostream>
  2. using namespace std;
  3. #define SIZE 10
  5. void create_heap(int *array,int n, int parent)
  6. {
  7.     int root;
  8.     int end;
  9.     int right;
  11.     root = array[parent];
  12.     end = parent;
  13.     right = 2*end +1;
  15.     while(right < n)
  16.     {
  17.         if( right<n-1  &&array[right]<array[right+1])
  18.         {
  19.             right++;
  20.         }
  22.         if(root<array[right])
  23.         {
  24.             array[end] = array[right];
  25.             end = right;
  26.             right = 2*end+1;
  27.         }
  28.         else{
  29.             break;
  30.         }
  31.     }
  32.     array[end] = root;
  33. }
  35. void Heap_Sort(int *array,int n)
  36. {
  37.     int i,end,key;
  38.     int *root;
  39.     for(i = n/2-1;i>=0;i++)
  40.     {
  41.         create_heap(array,n,i);
  42.     }
  44.     for(end = n-1;end>=1;end--)
  45.     {
  46.         key=array[0];
  47.         array[0] = array[end];
  48.         array[end] = key;
  50.         create_heap(array,end,0);
  51.     }
  52. }
  54. void Print(int *array)
  55. {
  56.     for(int i = 0; i<SIZE;i++)
  57.     {
  58.         cout<<array[i]<<" ,";
  59.     }
  61. }
  62. int main()
  63. {
  64.     int array[SIZE]={2,5,4,9,3,6,8,7,1,0};
  65.     int len = sizeof(array)/sizeof(array[0]);
  67.     Heap_Sort(array,len);
  68.     cout<<"堆排序结果为："<<endl;
  69.     Print(array);
  71.     return 0;
  72. }

（3）结果展示
这里写图片描述

五、排序算法的比较

（1）稳定性比较

  • 插入排序、冒泡排序、归并排序、以及其他线性排序是稳定的；
  • 选择排序、希尔排序、快速排序、堆排序是不稳定的；

（2）时间复杂度的比较

  • **O(n^2)**插入排序，冒泡排序、选择排序
  • **O(nlog2n)**堆排序，最优的快速排序

（3）辅助空间比较
归并排序为O(n)，其余为O(1)

发表评论

表情：
评论列表 （有 0 条评论，296人围观）

还没有评论，来说两句吧...

相关阅读