devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序类算法

作者：很楠不爱3 | 2024-03-12 12:04:47

赞

踩

排序类算法

目录

一、交换类排序

1.冒泡排序

2.快速排序

二、 插入排序

1.直接插入排序

2.折半插入排序

3.希尔排序

三、选择排序

1.简单选择排序

2.堆排序

 完整代码

四、归并排序

 完整代码

五、汇总

六、OJ练习 

        1.冒泡排序：正确表示前一个数和后一个数   

2.选择、堆、归并

完整代码 

一、交换类排序

1.冒泡排序

演示地址：

Comparison Sorting Visualization

 注意：n个数

1.交换条件 如果从小到大排列那么  判断 大数在前就发生交换

2.注意外层循环控制趟数 i从0 到  n-1趟    i++

3.注意内层循环控制遍历着进行交换  从后往前 n-1  到   i   j不能取0因为里面有j-1   j--

4.注意flag是看是否进行交换  经过一趟后没有发生交换则序列本身有序

  1. #include <stdio.h>
  2.  
  3.  
  4. void BubbleSort(int A[10],int n);
  5.  
  6. void swap(int &a,int &b){
  7.     int temp=a;
  8.     a=b;
  9.     b=temp;
  10. }
  11.  
  12. int main() {
  13.     int A[10]={9,7,8,6,5,4,3,2,1,0};
  14.     BubbleSort(A,10);
  15.     for (int i = 0; i < 10; ++i) {
  16.         printf("%2d",A[i]);
  17.     }
  18.     return 0;
  19. }
  20.  
  21. void BubbleSort(int A[10],int n) {
  22.     //控制趟数
  23.     for (int i = 0; i < n - 1; ++i) {
  24.         //交换标志
  25.         bool flag= false;
  26.         //控制交换
  27.         for (int j = n-1; j > i; j--) {
  28.             //从小到大排列 大的在前那么就要发生交换了
  29.             if (A[j-1]>A[j]){
  30.                 swap(A[j],A[j-1]);
  31.                 flag= true;
  32.             }
  33.         }
  34.         if (!flag){
  35.             //如果经过依次检查后没有发生交换则该数组本身有序
  36.             return;
  37.         }
  38.     }
  39. }

2.快速排序

注意：分治思想

        挖坑法（不断覆盖）得到分隔值的位置

        注意每次循环都要判断   low<high

        注意出现相等的数我们不用管--不需要处理

        最终low与high是相等的

演示地址：

Comparison Sorting Visualization

16.5 快速排序 

64, 94, 95, 79, 69, 84, 18, 22, 12 ,78

把比64小的放在64的左边，把比64大的放在它的右边
18, 22, 12 64  ,94, 95, 79, 69, 84,78

16.6 快速排序实战
原来的
64, 94, 95, 79, 69, 84, 18, 22, 12 ,78


pivot=64
12, 22, 18, 64, 69, 84, 79, 95, 94 ,78
                 high
                 low
pivot=64
12, 94, 95, 79, 69, 84, 18, 22, 12 ,78
                                               high
     low
 

  1. #include <stdio.h>
  2.  
  3. //得到分割值的位置--挖坑法（不断覆盖）
  4. int getPosition(int A[],int low,int high){
  5.     //把low的位置作为分隔值
  6.     int provt=A[low];
  7.     while (low<high){
  8.         //从high往前找比分隔值小的数的位置--注意循环里面也要判断low<high
  9.         while (low<high&&A[high]>=provt){
  10.             //没有找到就往前移动
  11.             high--;
  12.         }
  13.         //出循环 这时A[high]<provt  就找到了 这个小的元素
  14.         //我们需要把它覆盖到low的位置上
  15.         A[low]=A[high];
  16.         //从low往后找 直到找到比分隔值大的元素--注意循环里面也要判断low<high
  17.         while (low<high&&A[low]<=provt){
  18.             low++;
  19.         }
  20.         //此时A[low]>provt 找到了大的元素我们需要把它放到分割值的右边
  21.         //因此我们需要把它覆盖到high的位置上
  22.         A[high]=A[low];
  23.     }
  24.     //不要忘记把分隔值赋值上去
  25.     A[low]=provt;
  26.     //此时low=high的
  27.     return low;
  28. }
  29.  
  30.  
  31. //快速排序--分治思想
  32. void quickSort(int A[],int low,int high){
  33.     if (low>=high){
  34.         return;
  35.     }
  36.     //进行第一次快速排序得到分隔值的位置
  37.     int position=getPosition(A,low,high);
  38.     //接下来排列分隔值的左边
  39.     quickSort(A,low,position-1);
  40.     //接下来排列分隔值的右边
  41.     quickSort(A,position+1,high);
  42. }
  43.

二、 插入排序

1.直接插入排序

注意：

        外层循环控制：无序序列的个数--即要插入的元素个数  i从 1到len-1

        内层循环控制交换 注意条件 

        此时j的位置是从i-1开始 j>=0&&A[j]>inserVal 那么就将后面的元素进行覆盖

        注意最后要将j+1的位置即为要插入的位置

        因为循环完成后我们直到j这个位置是小于inserVal的所以要插入到这个位置的后面

16.7 插入排序的原理及实战

insertVal=1
                           i
    1 2 3 72 78      87 61 38 12 40
 j

  1. //玩坑法（覆盖）  插入排序
  2. void insertSort(int A[],int len){
  3.     int i,j,inserVal;
  4.     //注意循环起始  此时有序数列中左半边为1个元素  所以无序的右半边从 1开始到len-1
  5.     for (i = 1; i < len; ++i) {//外层循环控制要插入的数量
  6.         //存储当前要插入的值
  7.         inserVal=A[i];
  8.         //那么我们判断就从有序的开始  i-1  到0--并且这个元素大于要插入的元素那么就进行覆盖
  9.         for (j = i-1; j >=0&&A[j]>inserVal ; j--) {
  10.             //就将后面的元素覆盖成大的那一个
  11.             A[j+1]=A[j];
  12.         }
  13.         //最终要将插入元素进行插入-这里要使用到j因此要将j定义到循环外面
  14.         //如果最终j--到0了 那么此时将j+1的位置也就是0的位置即插入位置
  15.         A[j+1]=inserVal;
  16.     }
  17. }

2.折半插入排序

3.希尔排序

三、选择排序

1.简单选择排序

注意：

         内层循环：

        找到那么就记录该位置--必须写在这  因为我们要把后续的位置找全  找出最小
        如果写在循环条件处那么 它就会找到一个就交换一次  而不是最小才交换  注意最小条件

  1. //简单选择排序
  2. void selectSort(int A[],int len){
  3.     int min;
  4.     for (int i = 0; i < len - 1; ++i) {
  5.         //外层循环控制趟数
  6.         //每次都找出一个最小的 交换那么  只需要找len-1次
  7.         //记录最小值位置
  8.         min=i;
  9.         //内层循环从未确定的序列中找最小的位置 因此从i+1开始到结束
  10.         for (int j = i+1; j < len; ++j) {
  11.             //找到那么就记录该位置--必须写在这  因为我们要把后续的位置找全  找出最小
  12.             //如果写在循环条件处那么 它就会找到一个就交换一次  而不是最小才交换  注意最小条件
  13.             if (A[j]<A[min]){
  14.                 min=j;
  15.             }
  16.         }
  17.         //进行交换
  18.         swap(A[min],A[i]);
  19.     }
  20. }

2.堆排序


演示地址：Heap Sort Visualization

每次调整大根堆的时间复杂度为树的高度  调整n次  因此为n*logn

 

 

 注意：

        1.循环调整子树为大根堆的循环条件（son<len）--注意调整完后要重置dad与son

           因为这颗子树可能下面还有子树 

           我们需要让dad=son的 son=2*dad+1 这这颗子树也满足大根堆依次往复

        2.注意len是代表什么

        3.注意建立大根堆的循环条件  i是从最后一个父节点开始到0

        4.注意循环剩余元素为大根堆的循环条件 

        i代表无序的个数 i从len-1到1 直到调整到剩余俩个元素

 

 

  1. //交换
  2. void swap(int &a,int &b){
  3.     int temp=a;
  4.     a=b;
  5.     b=temp;
  6. }
  7.  
  8. /**
  9.  * 调整一个子树为大根堆
  10.  * @param A
  11.  * @param dad 最后一个节点的父节点位置
  12.  * @param len 需要调整的长度
  13.  */
  14. void adjustMaxTree(int A[],int last,int len){
  15.     int dad=last;
  16.     int son=2*dad+1;
  17.     while (son<len){
  18.         if (son+1<len&&A[son]<A[son+1]){
  19.             //比较左 右 孩子中最大的元素
  20.             //如果左孩子 小于 右孩子--最大元素为右孩子
  21.             son++;//拿右孩子
  22.         }
  23.         //得到最大元素为A[son]
  24.         if (A[son]>A[dad]){//如果孩子大于父亲 交换
  25.             //将孩子中最大的放到根节点上
  26.             swap(A[son],A[dad]);
  27.             //重置父子节点位置
  28.             dad=son;//son重新作为dad去验证下面的子树是否为大根堆--
  29.             son=2*dad+1;
  30.             //继续循环重新进行调整我们交换完的下面的那颗子树是否满足大根堆
  31.         } else{
  32.             //这个子树中的所有的子树全部满足大根堆
  33.             break;
  34.         }
  35.  
  36.     }
  37. }
  38.  
  39. //堆排序
  40. void heapSort(int A[],int len){
  41.     //建立大根堆
  42.     for (int i = len/2-1; i >= 0; i--) {
  43.         //从最后一个子树的父亲节点开始到0
  44.         adjustMaxTree(A,i,len);
  45.     }
  46.     //将最大元素放到数组末尾
  47.     swap(A[0],A[len-1]);
  48.     //调整剩余元素为大根堆并从小到大排列--调整到只剩2个元素
  49.     for (int i = len-1; i > 1; i--) {
  50.         //i代表的是无序的个数
  51.         //因为把最大的元素放到了最后一个树节点上 那么每次都要调整 父亲节点地址为0 长度为 i的元素为大跟堆
  52.         adjustMaxTree(A,0,i);
  53.         //调整之后进行交换--交换根部元素
  54.         swap(A[0],A[i-1]);
  55.     }
  56. }

 完整代码

  1. #include <stdio.h>
  2.  
  3.  
  4. //交换
  5. void swap(int &a,int &b){
  6.     int temp=a;
  7.     a=b;
  8.     b=temp;
  9. }
  10.  
  11. /**
  12.  * 调整一个子树为大根堆
  13.  * @param A
  14.  * @param dad 最后一个节点的父节点位置
  15.  * @param len 需要调整的长度
  16.  */
  17. void adjustMaxTree(int A[],int last,int len){
  18.     int dad=last;
  19.     int son=2*dad+1;
  20.     while (son<len){
  21.         if (son+1<len&&A[son]<A[son+1]){
  22.             //比较左 右 孩子中最大的元素
  23.             //如果左孩子 小于 右孩子--最大元素为右孩子
  24.             son++;//拿右孩子
  25.         }
  26.         //得到最大元素为A[son]
  27.         if (A[son]>A[dad]){//如果孩子大于父亲 交换
  28.             //将孩子中最大的放到根节点上
  29.             swap(A[son],A[dad]);
  30.             //重置父子节点位置
  31.             dad=son;//son重新作为dad去验证下面的子树是否为大根堆--
  32.             son=2*dad+1;
  33.             //继续循环重新进行调整我们交换完的下面的那颗子树是否满足大根堆
  34.         } else{
  35.             //这个子树中的所有的子树全部满足大根堆
  36.             break;
  37.         }
  38.  
  39.     }
  40. }
  41.  
  42. //堆排序
  43. void heapSort(int A[],int len){
  44.     //建立大根堆
  45.     for (int i = len/2-1; i >= 0; i--) {
  46.         //从最后一个子树的父亲节点开始到0
  47.         adjustMaxTree(A,i,len);
  48.     }
  49.     //将最大元素放到数组末尾
  50.     swap(A[0],A[len-1]);
  51.     //调整剩余元素为大根堆并从小到大排列--调整到只剩2个元素
  52.     for (int i = len-1; i > 1; i--) {
  53.         //i代表的是无序的个数
  54.         //因为把最大的元素放到了最后一个树节点上 那么每次都要调整 父亲节点地址为0 长度为 i的元素为大跟堆
  55.         adjustMaxTree(A,0,i);
  56.         //调整之后进行交换--交换根部元素
  57.         swap(A[0],A[i-1]);
  58.     }
  59. }
  60.  
  61. int main() {
  62.     int A[10]={58,42,13,58,44,53,73,75,2,69};
  63.     int len=10;
  64.     heapSort(A,len);
  65.     for (int i = 0; i < 10; ++i) {
  66.         printf("%3d",A[i]);
  67.     }
  68.     return 0;
  69. }

四、归并排序

注意：

        1.复制临时数组  static int B[N];

        2.复制的时候for循环从low开始  避免覆盖掉之前的元素

        3.合并的时候  注意合并的那个数组A  k是从low开始  避免覆盖掉之间的元素

        4.不要忘记 剩余元素的合并

  1. #define N 50
  2.  
  3. void merge(int A[],int low,int mid,int high){
  4.     //注意static无论递归多少次都只有一个B
  5.     static int  B[N];
  6.     //复制临时数组--注意这里是low 到high
  7.     for (int i = low; i <= high; ++i) {
  8.         B[i]=A[i];
  9.     }
  10.     int i,j,k;
  11.     //注意k是从low开始
  12.     for ( i = low,j=mid+1,k=low;i<=mid&&j<=high; k++) {
  13.         //i j 的元素值进行比较 小的放入A中--并且放入的元素的那个向后移动
  14.         if (B[i]<B[j]){
  15.             A[k]=B[i++];
  16.         } else{
  17.             A[k]=B[j++];
  18.         }
  19.     }
  20.     //看哪个有剩余都放入到A中即可
  21.     while (i<=mid){
  22.         A[k++]=B[i++];
  23.     }
  24.     while (j<=high){
  25.         A[k++]=B[j++];
  26.     }
  27. }
  28.  
  29. void mergeSort(int A[],int low,int high){
  30.     if (low<high){
  31.         int mid=(low+high)/2;
  32.         //排序前半边
  33.         mergeSort(A,low,mid);
  34.         //排序号后半边
  35.         mergeSort(A,mid+1,high);
  36.         //合并为有序数组
  37.         merge(A,low,mid,high);
  38.     }
  39. }

 完整代码

  1. #include <stdio.h>
  2.  
  3. #define N 50
  4.  
  5. void merge(int A[],int low,int mid,int high){
  6.     //注意static无论递归多少次都只有一个B
  7.     static int  B[N];
  8.     //复制临时数组--注意这里是low 到high
  9.     for (int i = low; i <= high; ++i) {
  10.         B[i]=A[i];
  11.     }
  12.     int i,j,k;
  13.     //注意k是从low开始
  14.     for ( i = low,j=mid+1,k=low;i<=mid&&j<=high; k++) {
  15.         //i j 的元素值进行比较 小的放入A中--并且放入的元素的那个向后移动
  16.         if (B[i]<B[j]){
  17.             A[k]=B[i++];
  18.         } else{
  19.             A[k]=B[j++];
  20.         }
  21.     }
  22.     //看哪个有剩余都放入到A中即可
  23.     while (i<=mid){
  24.         A[k++]=B[i++];
  25.     }
  26.     while (j<=high){
  27.         A[k++]=B[j++];
  28.     }
  29. }
  30.  
  31. void mergeSort(int A[],int low,int high){
  32.     if (low<high){
  33.         int mid=(low+high)/2;
  34.         //排序前半边
  35.         mergeSort(A,low,mid);
  36.         //排序号后半边
  37.         mergeSort(A,mid+1,high);
  38.         //合并为有序数组
  39.         merge(A,low,mid,high);
  40.     }
  41. }
  42.  
  43. int main() {
  44.     int A[10]={58,42,13,58,44,53,73,75,2,69};
  45.     int low=0,high=9;
  46.     mergeSort(A,low,high);
  47.     for (int i = 0; i <10; ++i) {
  48.         printf("%3d",A[i]);
  49.     }
  50.     return 0;
  51. }

五、汇总

六、OJ练习 

注意：

        1.冒泡排序：正确表示前一个数和后一个数   

        j--

  1. #include <stdio.h>
  2.  
  3. //读取10个整型数据12 63 58 95 41 35 65  0 38 44，
  4. // 然后通过冒泡排序，快速排序，插入排序，分别对该组数据进行排序，输出3次有序结果，每个数的输出占3个空格
  5.  
  6. //交换
  7. void swap(int &a,int &b){
  8.     int temp=a;
  9.     a=b;
  10.     b=temp;
  11. }
  12.  
  13. void print_A(int A[],int len){
  14.     //排序完成
  15.     for (int i = 0; i < len; ++i) {
  16.         printf("%3d",A[i]);
  17.     }
  18.     printf("\n");
  19. }
  20.  
  21. //冒泡排序
  22. void BubbleSort(int A[],int len){
  23.     bool flag= false;
  24.     for (int i = 0; i < len ; ++i) {
  25.         for (int j = len-1; j > i; j--) {
  26.             //从小到大 如果前面比后面大交换
  27.             if (A[j-1]>A[j]){
  28.                 swap(A[j-1],A[j]);
  29.                 flag= true;
  30.             }
  31.         }
  32.         if (!flag){
  33.             return;
  34.         }
  35.     }
  36.     print_A(A,len);
  37. }
  38.  
  39. //挖坑法--分割
  40. int patition(int A[],int low,int high){
  41.     //先将low的位置作为分割值
  42.     int provt=A[low];
  43.     while (low<high){
  44.         //从后往前找比分隔值小的数进行覆盖
  45.         while (low<high&&A[high]>=provt){
  46.             high--;
  47.         }
  48.         //此时A[high]<provt
  49.         A[low]=A[high];
  50.         //从前往后找比分隔值大数进行覆盖
  51.         while (low<high&&A[low]<=provt){
  52.             low++;
  53.         }
  54.         //此时A[low]>provt
  55.         A[high]=A[low];
  56.     }
  57.     //填入分隔值
  58.     A[low]=provt;
  59.     return low;
  60. }
  61.  
  62. //快速排序--分治
  63. void quickSort(int A[],int low,int high){
  64.     if (low>high){
  65.         return;
  66.     }
  67.     //确定一个分割位置
  68.     int position=patition(A,low,high);
  69.     //排序左边
  70.     quickSort(A,low,position-1);
  71.     //排序右边
  72.     quickSort(A,position+1,high);
  73. }
  74.  
  75. //插入排序
  76. void inserSort(int A[],int len){
  77.     int i,j,insertVal;
  78.     for (i = 1; i < len; ++i) {
  79.         insertVal=A[i];
  80.         for (j = i-1; j >=0&&A[j]>insertVal; j--) {
  81.             //交换
  82.             A[j+1]=A[j];
  83.         }
  84.         //插入
  85.         A[j+1]=insertVal;
  86.     }
  87.     print_A(A,len);
  88. }
  89.  
  90.  
  91. int main() {
  92.     int A[10];
  93.     for (int i = 0; i < 10; ++i) {
  94.         int x;
  95.         scanf("%d",&x);
  96.         A[i]=x;
  97.     }
  98.     int len=10;
  99.     BubbleSort(A,len);
  100.     quickSort(A,0,len-1);
  101.     print_A(A,len);
  102.     inserSort(A,len);
  103.     return 0;
  104. }

2.选择、堆、归并

选择排序：注意  找到最小的后是交换 而不是覆盖

堆排序：  注意第一次建立完大根堆后  将根节点(最大)与最后一个节点进行交换

                然后再依次进行 大根堆的建立 建立的时候 因为最后都改变了根节点与最后一个元                  素的值  那么每次建立大根堆的父节点都是从0开始  注意起始条件

归并排序：注意不要忘记剩余节点也要合为一个数组

  1. //交换
  2. void swap(int &a,int &b){
  3.     int temp=a;
  4.     a=b;
  5.     b=temp;
  6. }
  7.  
  8. //选择排序--找最小的放到前面/找最大的放到后面
  9. void SelectSort(int A[],int len){
  10.     int i=0,min,j;
  11.     int temp=A[i];
  12.     while (i<len){
  13.         min=i;
  14.         for (j = i+1; j < len; ++j) {
  15.             if (A[min]>A[j]){
  16.                 min=j;
  17.             }
  18.         }
  19.         //找到了最小值
  20.         swap(A[i++],A[min]);
  21.     }
  22. }
  23.  
  24. //建立大根堆
  25. void buildMaxTree(int A[],int last,int len){
  26.     int dad=last;
  27.     int son=last*2+1;
  28.     while (son<len){
  29.         if (son+1<len&&A[son]<A[son+1]){
  30.             son++;//拿到右孩子作为最大
  31.         }
  32.         //最大的孩子节点值与父节点比较替换
  33.         if (A[son]>A[dad]){
  34.             swap(A[son],A[dad]);
  35.             //重置dad与son 为下一个子树
  36.             dad=son;
  37.             son=2*dad+1;
  38.         } else{
  39.             //全部变为大根堆 没有任何交换后--退出循环
  40.             break;
  41.         }
  42.     }
  43. }
  44.  
  45. //堆排序
  46. void heapSort(int A[],int len){
  47.     //对于初始数组建立大根堆
  48.     for (int i = len/2-1; i >= 0; i--) {
  49.         buildMaxTree(A,i,len);
  50.     }
  51.     //之后交换根节点与最后一个节点
  52.     swap(A[0],A[len-1]);
  53.     //堆剩余元素进行大根堆的依次建立--直到仅剩余2个节点
  54.     for (int i = len-1; i >1 ; i--) {//i为当今剩余的无序节点数量
  55.         //因为交换了 那么改变的就是A[0]节点开始 的大根堆--因此此时父节点为0
  56.         buildMaxTree(A,0,i);
  57.         //交换改变
  58.         swap(A[0],A[i-1]);
  59.         //继续上述操作
  60.     }
  61. }
  62. //归并排序--合并有序数组
  63. void merge(int A[],int low,int mid,int high){
  64.     static int B[N];
  65.     for (int i = low; i <= high; ++i) {
  66.         B[i]=A[i];
  67.     }
  68.     int i,j,k;
  69.     for (i = low,j=mid+1,k=low;i<=mid&&j<=high; k++) {
  70.         if (B[i]<B[j]){
  71.             A[k]=B[i++];
  72.         } else{
  73.             A[k]=B[j++];
  74.         }
  75.     }
  76.     //不要忘记还有剩余元素
  77.     while (i<=mid){
  78.         A[k++]=B[i++];
  79.     }
  80.     while (j<=high){
  81.         A[k++]=B[j++];
  82.     }
  83. }
  84. //归并排序
  85. void mergeSort(int A[],int low,int high){
  86.     if (low>=high){
  87.         return;
  88.     }
  89.     int mid=(low+high)/2;
  90.     //归并前半部分
  91.     mergeSort(A,low,mid);
  92.     //归并后半部分
  93.     mergeSort(A,mid+1,high);
  94.     //合并为有序数列
  95.     merge(A,low, mid,high);
  96. }
  97.  
  98. void printSort(int A[],int len){
  99.     for (int i = 0; i < len; ++i) {
  100.         printf("%3d",A[i]);
  101.     }
  102. }

完整代码 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/224017
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号