• 【算法】排序——冒泡排序

    目录

    一、插入排序

    二、冒泡排序

    三、选择排序

    四、希尔排序

    五、快速排序

    六、堆排序

    附：系列文章

    内部排序的全部过程都是在内存中进行的。按排序策略的不同可以将内部排序划分为插入排序、冒泡排序、选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。其中前三种排序方法属于简单的排序方法，其特点是排序过程直观、易于理解和实现，都属于稳定的排序方法，但效率较低；其他几种方法则称为先进的排序方法，算法原理相对复杂，不稳定，但效率较高。

    一、插入排序

    （1）直接插入排序的基本思想是把新的未排序的元素逐个插入已排序的有序表种。直接插入排序算法可以借助减治法的减一技术进行设计。

    （2）假设待排序序列中有k个元素（1<=k<=N-2）已经按照关键字值递增顺序排列，将一个未排序的元素list[i]（1<=i<=N-1）直接插入适当的位置。整个排序过程进行N-1趟插入，即首先从右向左顺序搜索表中已排序的序列，直到找到一个元素list[j-1]（1<=j-1<=k-1）的关键字值比list[i]的关键字值小；将已排序序列中比list[i]的关键字值大的元素list[j]，list[i+1]，……，list[k]依次在线性表中后移一个位置；将元素list[i]插入表中的j的位置上成为元素list[j]。 

    插入排序算法

    1. void insertSort(int list[],int n){
    2.     int i,j;
    3.     for(i=2;i<=n;i++){
    4.         list[0]=list[i];
    5.         j=i-1;
    6.         while(j>0&&list[0]
    7.             list[j+1]=list[j];
    8.             --j;
    9.         }
    10.         list[j+1]=list[0];
    11.     }
    12. }  

    完整程序

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. int main(){
    17.     int i,n;
    18.     scanf("%d",&n);
    19.     for(i=1;i<=n;i++){
    20.         scanf("%d",&list[i]);
    21.     }
    22.     insertSort(list,n);
    23.     for(i=1;i<=n;i++){
    24.         printf("%d ",list[i]);
    25.     } 
    26.     return 0;
    27. } 

    二、冒泡排序

    （1）冒泡排序的基本思想是在排序过程中，对待排序序列中相邻两个元素关键字的值进行比较，当不满足排序要求时就交换两个元素的位置。这样，关键字值较小的元素就会像水中的气泡一样逐层浮起，直至完成排序过程。利用蛮力法容易实现冒泡排序的算法涉及。

    （2）在某一遍扫描中，对元素list[i]与list[i+1]的关键字进行比较，若list[i]>list[i+1]，则交换list[i]与list[i+1]的位置，这样重复扫描，直到在某一遍扫描时不存在list[i]>list[i+1]的情况，排序结束。

    （3）在经过一次扫描后，关键字最大的元素就沉底了，排到了线性表的最后一个位置，且在比较过程中，凡是关键字较小的元素都浮上了一层。在第i+1次扫描时，不必自上而下的比较线性表中所有的相邻元素对，只需要比较从list[1]到list[N-1]的相邻元素就可以了，这是因为经过i次扫描后，线性表中元素list[N-i+1]到list[N]的元素都已经在正确的位置了，不必再次扫描。实际排序过程中，如果经过k趟冒泡排序后，就已经排好序了，就不必继续进行后序的排序，为此可以设置一个标志flag，用来记录每趟扫描是否还存在元素的交换，若已经没有元素的交换，则排序可以提前结束。

    冒泡排序算法

    1. void bubbleSort(int list[],int n){
    2.     int i=1,j,t,flag=1;
    3.     for(i=1;i
    4.         flag=0;
    5.         for(j=1;j<=n-1;j++){
    6.             if(list[j]>list[j+1]){
    7.                 t=list[j];
    8.                 list[j]=list[j+1];
    9.                 list[j+1]=t;
    10.                 flag=1;
    11.             }
    12.         }
    13.     }
    14. } 

    完整程序 

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. void bubbleSort(int list[],int n){
    17.     int i=1,j,t,flag=1;
    18.     for(i=1;i
    19.         flag=0;
    20.         for(j=1;j<=n-1;j++){
    21.             if(list[j]>list[j+1]){
    22.                 t=list[j];
    23.                 list[j]=list[j+1];
    24.                 list[j+1]=t;
    25.                 flag=1;
    26.             }
    27.         }
    28.     }
    29. }
    30. int main(){
    31.     int i,n;
    32.     scanf("%d",&n);
    33.     for(i=1;i<=n;i++){
    34.         scanf("%d",&list[i]);
    35.     }
    36.     //insertSort(list,n);
    37.     bubbleSort(list,n);
    38.     for(i=1;i<=n;i++){
    39.         printf("%d ",list[i]);
    40.     } 
    41.     return 0;
    42. } 

    三、选择排序

    （1）简单选择排序的基本思想来自人们对排序过程最直接的认识：不断从待排序序列中挑选出关键字最小的元素，依次放在已排序子序列的最后，直到待排序序列中所有元素都被选完，从而得到一个有序的序列。选择排序算法的设计同样可以借助蛮力法进行。 

    （2）设待排序线性表为L，选择排序过程共需执行N-1遍操作，具体步骤如下：

    ① 在第i次挑选中（1<=i<=N-1）重复下述过程：让元素L[i]依次与元素L[i+1]，L[i+2]，……L[N]比较，如果L[i].key>L[j].key(i<=j<=N)，就交换元素L[i]与L[j]在线性表中的位置。

    ② i=i+1，重复步骤①

    选择排序的算法

    1. void SelectSort(int list[],int n){
    2.     int i,j,k,temp;
    3.     for(i=1;i<=n-1;++i){
    4.         k=i;
    5.         for(j=i+1;j<=n;j++){
    6.             if(list[j]
    7.             k=j;
    8.         }
    9.         if(i!=k){
    10.             temp=list[i];
    11.             list[i]=list[k];
    12.             list[k]=temp;
    13.         }
    14.     }
    15. } 

    完整程序

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. void bubbleSort(int list[],int n){
    17.     int i=1,j,t,flag=1;
    18.     for(i=1;i
    19.         flag=0;
    20.         for(j=1;j<=n-1;j++){
    21.             if(list[j]>list[j+1]){
    22.                 t=list[j];
    23.                 list[j]=list[j+1];
    24.                 list[j+1]=t;
    25.                 flag=1;
    26.             }
    27.         }
    28.     }
    29. }
    30. void SelectSort(int list[],int n){
    31.     int i,j,k,temp;
    32.     for(i=1;i<=n-1;++i){
    33.         k=i;
    34.         for(j=i+1;j<=n;j++){
    35.             if(list[j]
    36.             k=j;
    37.         }
    38.         if(i!=k){
    39.             temp=list[i];
    40.             list[i]=list[k];
    41.             list[k]=temp;
    42.         }
    43.     }
    44. } 
    45. int main(){
    46.     int i,n;
    47.     scanf("%d",&n);
    48.     for(i=1;i<=n;i++){
    49.         scanf("%d",&list[i]);
    50.     }
    51.     //insertSort(list,n);
    52.     //bubbleSort(list,n);
    53.     SelectSort(list,n);
    54.     for(i=1;i<=n;i++){
    55.         printf("%d ",list[i]);
    56.     } 
    57.     return 0;
    58. } 

    四、希尔排序

    （1）希尔排序又称缩小增量排序，是对直接插入排序的改进方法。它的基本思想是，将整个待排序序列分割为若干个较小的子序列分别进行排序；在待排序序列的记录达到基本有序时再对整个序列进行一次排序。希尔排序子序列的构成不是简单地逐段分割，而是将相隔某个增量的记录组成一个子序列。

    （2）希尔排序的主要步骤：

    ① 首先确定一个整数d1

    ② 再继续选择d2

    ③ 继续取di+1

    （3）希尔排序中各组中的排序可以采用直接插入排序，但是排序速度要比直接插入速度快得多。当di取值大时，组内元素个数少，排序速度快，随着di的逐渐减小，组内元素个数增多，但是各元素已接近最终的排序位置，所以位置的调整不需要很多，因而整个希尔排序速度比直接插入排序速度快。

    希尔排序算法 

    1. void Shellinsert(int list[],int dk,int n){
    2.     int i,j;
    3.     for(i=dk+1;i<=n;i++){
    4.         if(list[i]
    5.             list[0]=list[i];
    6.             for(j=i-dk;j>0&&list[0]
    7.                 list[j+dk]=list[j];
    8.             }
    9.             list[j+dk]=list[0];
    10.         }
    11.     }
    12. }
    13. void ShellSort(int list[],int dlta[],int t,int n){
    14.     int i,k;
    15.     for(k=0;k
    16.         Shellinsert(list,dlta[k],n);
    17.     }
    18. }

    完整程序

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. void bubbleSort(int list[],int n){
    17.     int i=1,j,t,flag=1;
    18.     for(i=1;i
    19.         flag=0;
    20.         for(j=1;j<=n-1;j++){
    21.             if(list[j]>list[j+1]){
    22.                 t=list[j];
    23.                 list[j]=list[j+1];
    24.                 list[j+1]=t;
    25.                 flag=1;
    26.             }
    27.         }
    28.     }
    29. }
    30. void SelectSort(int list[],int n){
    31.     int i,j,k,temp;
    32.     for(i=1;i<=n-1;++i){
    33.         k=i;
    34.         for(j=i+1;j<=n;j++){
    35.             if(list[j]
    36.             k=j;
    37.         }
    38.         if(i!=k){
    39.             temp=list[i];
    40.             list[i]=list[k];
    41.             list[k]=temp;
    42.         }
    43.     }
    44. } 
    45. void Shellinsert(int list[],int dk,int n){
    46.     int i,j;
    47.     for(i=dk+1;i<=n;i++){
    48.         if(list[i]
    49.             list[0]=list[i];
    50.             for(j=i-dk;j>0&&list[0]
    51.                 list[j+dk]=list[j];
    52.             }
    53.             list[j+dk]=list[0];
    54.         }
    55.     }
    56. }
    57. void ShellSort(int list[],int dlta[],int t,int n){
    58.     int i,k;
    59.     for(k=0;k
    60.         Shellinsert(list,dlta[k],n);
    61.     }
    62. }
    63. int main(){
    64.     int i,n;
    65.     scanf("%d",&n);
    66.     for(i=1;i<=n;i++){
    67.         scanf("%d",&list[i]);
    68.     }
    69.     //insertSort(list,n);
    70.     //bubbleSort(list,n);
    71.     //SelectSort(list,n);
    72.     int dlta[3]={5,3,1};
    73.     ShellSort(list,dlta,3,n);
    74.     for(i=1;i<=n;i++){
    75.         printf("%d ",list[i]);
    76.     } 
    77.     return 0;
    78. }

    五、快速排序

    （1）快速排序是对冒泡排序的一种改进。基本思想是，通过一趟排序将待记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。利用分治法容易实现快速排序的算法设计

    （2）选取第一个元素的关键字作为界值讨论快速排序的算法

    ① 设置两个指针left和right，分别从表的两端向中间移动，将界值元素放入一个暂存单元

    ② 将指针right对序列自右向左扫描，直到找到一个关键字小于界值的元素，将该元素移至left指针所在位置

    ③ 将指针left对序列自左向右扫描，直到找到一个关键字大于或等于界值的元素，将其放入right指针所指位置。

    ④ 重复步骤②和③，直到指针left和right相遇，此时，指针所在位置的左边元素关键字值均小于界值，右边所有元素关键字值均大于等于界值。将界值元素放入指针相遇位置

    ⑤ 对产生的两个子序列，再进行如上所述的划分，直到所有子序列中只有一个元素为止。

    快速排序算法 

    1. int Partition(int list[],int low,int high){
    2.     int pivotkey;
    3.     list[0]=list[low];
    4.     pivotkey=list[low];
    5.     while(low
    6.         while(low=pivotkey){
    7.             --high;
    8.         }
    9.         list[low]=list[high];
    10.         while(low
    11.             ++low;
    12.         }
    13.         list[high]=list[low];
    14.     }
    15.     list[low]=list[0];
    16.     return low;
    17. }
    18. void QSort(int list[],int low,int high){
    19.     int pivotloc,i,pivotkey;
    20.     pivotkey=list[low];
    21.     if(low
    22.         pivotloc=Partition(list,low,high);
    23.         QSort(list,low,pivotloc-1);
    24.         QSort(list,pivotloc+1,high);
    25.     }
    26. } 

    完整程序

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. void bubbleSort(int list[],int n){
    17.     int i=1,j,t,flag=1;
    18.     for(i=1;i
    19.         flag=0;
    20.         for(j=1;j<=n-1;j++){
    21.             if(list[j]>list[j+1]){
    22.                 t=list[j];
    23.                 list[j]=list[j+1];
    24.                 list[j+1]=t;
    25.                 flag=1;
    26.             }
    27.         }
    28.     }
    29. }
    30. void SelectSort(int list[],int n){
    31.     int i,j,k,temp;
    32.     for(i=1;i<=n-1;++i){
    33.         k=i;
    34.         for(j=i+1;j<=n;j++){
    35.             if(list[j]
    36.             k=j;
    37.         }
    38.         if(i!=k){
    39.             temp=list[i];
    40.             list[i]=list[k];
    41.             list[k]=temp;
    42.         }
    43.     }
    44. } 
    45. void Shellinsert(int list[],int dk,int n){
    46.     int i,j;
    47.     for(i=dk+1;i<=n;i++){
    48.         if(list[i]
    49.             list[0]=list[i];
    50.             for(j=i-dk;j>0&&list[0]
    51.                 list[j+dk]=list[j];
    52.             }
    53.             list[j+dk]=list[0];
    54.         }
    55.     }
    56. }
    57. void ShellSort(int list[],int dlta[],int t,int n){
    58.     int i,k;
    59.     for(k=0;k
    60.         Shellinsert(list,dlta[k],n);
    61.     }
    62. }
    63. int Partition(int list[],int low,int high){
    64.     int pivotkey;
    65.     list[0]=list[low];
    66.     pivotkey=list[low];
    67.     while(low
    68.         while(low=pivotkey){
    69.             --high;
    70.         }
    71.         list[low]=list[high];
    72.         while(low
    73.             ++low;
    74.         }
    75.         list[high]=list[low];
    76.     }
    77.     list[low]=list[0];
    78.     return low;
    79. }
    80. void QSort(int list[],int low,int high){
    81.     int pivotloc,i,pivotkey;
    82.     pivotkey=list[low];
    83.     if(low
    84.         pivotloc=Partition(list,low,high);
    85.         QSort(list,low,pivotloc-1);
    86.         QSort(list,pivotloc+1,high);
    87.     }
    88. }
    89. int main(){
    90.     int i,n;
    91.     scanf("%d",&n);
    92.     for(i=1;i<=n;i++){
    93.         scanf("%d",&list[i]);
    94.     }
    95.     //insertSort(list,n);
    96.     //bubbleSort(list,n);
    97.     //SelectSort(list,n);
    98.     int dlta[3]={5,3,1};
    99.     //ShellSort(list,dlta,3,n);
    100.     QSort(list,1,n);
    101.     for(i=1;i<=n;i++){
    102.         printf("%d ",list[i]);
    103.     } 
    104.     return 0;
    105. } 

    六、堆排序

    （1）堆排序是对简单选择排序的改进方法。堆排序的特点在于即使在最坏情况下，它的时间复杂度仍然为O(log2N)，而且只需要一个记录大小的辅助空间，即空间复杂度为O(1) 

    （2）堆排序的算法过程描述：

    ① 建立一个初始堆。调整线性表L中的元素L[1]，L[2]，……，L[[N/2]]，使所有元素构成一个堆。这时L[1]为堆中关键字值最大的结点。

    ② 把堆中结点L[N]与L[1]交换，得到由L[1]，L[2]，……，L[N-1]构成的类堆。

    ③ 将类堆L[1]，L[2]，……L[N-1]转化为一个堆。

    ④ 重复步骤②，步骤③，直到整个线性表被排序完毕

    （3）堆排序初看排序效率不高，因为在堆排序过程中，关键字较大的结点先移到线性表左边的位置，最后又放在线性表右边的位置上。实验证明，当N较小时这个方法不适合，但当N较大时，堆排序算法效率较高，可达到仅次于快速排序的排序效率。  

    堆排序算法

    1. void heapAdjust(int list[],int u,int v){
    2.     int i=u,j,temp=list[i];
    3.     j=2*i;
    4.     while(j<=v){
    5.         if(j1]){
    6.             j++;
    7.         }
    8.         if(temp
    9.             list[i]=list[j];
    10.             i=j;
    11.             j=2*i;
    12.         }else{
    13.             break;
    14.         }
    15.     }
    16.     list[i]=temp;
    17. }
    18. void heapSort(int list[],int n){
    19.     int i=0;
    20.     for(i=n/2;i>0;i--){
    21.         heapAdjust(list,i,n);
    22.     }
    23.     for(i=n;i>1;i--){
    24.         list[0]=list[1];
    25.         list[1]=list[i];
    26.         list[i]=list[0];
    27.         heapAdjust(list,1,i-1);
    28.     }
    29. } 

    完整程序 

    1. #include
    2. #define N 20
    3. int list[N+1];
    4. void insertSort(int list[],int n){
    5.     int i,j;
    6.     for(i=2;i<=n;i++){
    7.         list[0]=list[i];
    8.         j=i-1;
    9.         while(j>0&&list[0]
    10.             list[j+1]=list[j];
    11.             j--;
    12.         }
    13.         list[j+1]=list[0];
    14.     }
    15. }
    16. void bubbleSort(int list[],int n){
    17.     int i=1,j,t,flag=1;
    18.     for(i=1;i
    19.         flag=0;
    20.         for(j=1;j<=n-1;j++){
    21.             if(list[j]>list[j+1]){
    22.                 t=list[j];
    23.                 list[j]=list[j+1];
    24.                 list[j+1]=t;
    25.                 flag=1;
    26.             }
    27.         }
    28.     }
    29. }
    30. void SelectSort(int list[],int n){
    31.     int i,j,k,temp;
    32.     for(i=1;i<=n-1;++i){
    33.         k=i;
    34.         for(j=i+1;j<=n;j++){
    35.             if(list[j]
    36.             k=j;
    37.         }
    38.         if(i!=k){
    39.             temp=list[i];
    40.             list[i]=list[k];
    41.             list[k]=temp;
    42.         }
    43.     }
    44. } 
    45. void Shellinsert(int list[],int dk,int n){
    46.     int i,j;
    47.     for(i=dk+1;i<=n;i++){
    48.         if(list[i]
    49.             list[0]=list[i];
    50.             for(j=i-dk;j>0&&list[0]
    51.                 list[j+dk]=list[j];
    52.             }
    53.             list[j+dk]=list[0];
    54.         }
    55.     }
    56. }
    57. void ShellSort(int list[],int dlta[],int t,int n){
    58.     int i,k;
    59.     for(k=0;k
    60.         Shellinsert(list,dlta[k],n);
    61.     }
    62. }
    63. int Partition(int list[],int low,int high){
    64.     int pivotkey;
    65.     list[0]=list[low];
    66.     pivotkey=list[low];
    67.     while(low
    68.         while(low=pivotkey){
    69.             --high;
    70.         }
    71.         list[low]=list[high];
    72.         while(low
    73.             ++low;
    74.         }
    75.         list[high]=list[low];
    76.     }
    77.     list[low]=list[0];
    78.     return low;
    79. }
    80. void QSort(int list[],int low,int high){
    81.     int pivotloc,i,pivotkey;
    82.     pivotkey=list[low];
    83.     if(low
    84.         pivotloc=Partition(list,low,high);
    85.         QSort(list,low,pivotloc-1);
    86.         QSort(list,pivotloc+1,high);
    87.     }
    88. }
    89. void heapAdjust(int list[],int u,int v){
    90.     int i=u,j,temp=list[i];
    91.     j=2*i;
    92.     while(j<=v){
    93.         if(j1]){
    94.             j++;
    95.         }
    96.         if(temp
    97.             list[i]=list[j];
    98.             i=j;
    99.             j=2*i;
    100.         }else{
    101.             break;
    102.         }
    103.     }
    104.     list[i]=temp;
    105. }
    106. void heapSort(int list[],int n){
    107.     int i=0;
    108.     for(i=n/2;i>0;i--){
    109.         heapAdjust(list,i,n);
    110.     }
    111.     for(i=n;i>1;i--){
    112.         list[0]=list[1];
    113.         list[1]=list[i];
    114.         list[i]=list[0];
    115.         heapAdjust(list,1,i-1);
    116.     }
    117. }
    118. int main(){
    119.     int i,n;
    120.     scanf("%d",&n);
    121.     for(i=1;i<=n;i++){
    122.         scanf("%d",&list[i]);
    123.     }
    124.     //insertSort(list,n);
    125.     //bubbleSort(list,n);
    126.     //SelectSort(list,n);
    127.     int dlta[3]={5,3,1};
    128.     //ShellSort(list,dlta,3,n);
    129.     //QSort(list,1,n);
    130.     heapSort(list,n);
    131.     for(i=1;i<=n;i++){
    132.         printf("%d ",list[i]);
    133.     } 
    134.     return 0;
    135. }

    附：系列文章

    序号文章目录直达链接
    1栈https://want595.blog.csdn.net/article/details/127154749
    2队列https://want595.blog.csdn.net/article/details/127816577
    3串https://want595.blog.csdn.net/article/details/128784134
    4数组https://want595.blog.csdn.net/article/details/127380551
    5广义表https://want595.blog.csdn.net/article/details/127395781
    6树https://want595.blog.csdn.net/article/details/127454209
    7图https://want595.blog.csdn.net/article/details/127901532
    8查找https://want595.blog.csdn.net/article/details/128769694
    9排序https://want595.blog.csdn.net/article/details/128156174

     

  • 相关阅读:
    程序员写出代码版《本草纲目》毽子操，刘畊宏回复：很cool
    QRegExp（正则表达式）
    实际项目中如何进行问题排查
    OpenCV、PIL知识点日常总结【持续更新......】
    22. 深度学习 - 自动求导
    当AI遇到IoT：开启智能生活的无限可能
    Realtime Data Processing at Facebook
    LeetCode中等题之替换字符串中的括号内容
    springcloud二手交易平台系统源码
    django 内置 JSON 字段 使用场景
  • 原文地址：https://blog.csdn.net/m0_68111267/article/details/128156174