f Oracle-排序算法复习 - Powered by qidao123.com技术社区

排序算法复习

羊蹓狼  论坛元老 | 2025-4-1 02:54:27 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1802|帖子 1802|积分 5406

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
排序算法分为交换类排序，插入类排序，选择类排序，归并类排序
交换排序分为   冒泡排序和快速排序
1.冒泡排序
   1、思路：通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比力，若发现前一个数大于后一个数则交换，使值较大的元素渐渐从前移向后部，就如果水底下的气泡一样渐渐向上冒。
  2、先以一个数组讲解一下，然后再写代码：
      待排序数组：3，9，-1，10，20
       第一轮排序：
        （1）3，9，-1，10，20      ----3跟9比力，不交换
          （2）3，-1，9，10，20      ----9比 -1大，以是9跟 -1交换
          （3）3，-1，9，10，20      ----9跟10比力，不交换
          （4）3，-1，9，10，20      ----10跟20比力，不交换
             第一轮事后，将20这个最大的元素固定到了最后的位置。
             在第二轮的时间20不参与冒泡。
         第二轮排序：
            由于20的位置已经固定，以是只对前4个进行排序即可：
          （1）-1，3，9，10，20      ----3比 -1大，进行交换
          （2）-1，3，9，10，20      ----3跟9比力，不交换
          （3）-1，3，9，10，20      ----9跟10比力，不交换
              第二轮事后，将第二大的元素固定到了倒数第二个位置
         第三轮排序：
            10和20的位置已经确定，只需对前三个进行排序
          （1）-1，3，9，10，20      ----3和-1比力，不交换
          （2）-1，3，9，10，20      ----3和9比力，不交换
              第三轮事后，将第三大的元素位置确定
         第四轮排序：
            只对前两个元素进行排序
          （1）-1，3，9，10，20      ----3和-1比力，不交换
         第四轮事后，将第四大的元素位置确定，此时统共5个元素，已经排序好4个，从而最后一个天然而然就是排好序的了
  小结：
设总的元素个数为n，那么由上边的排序过程可以看出：
  （1）总计必要进行（n-1）轮排序，也就是（n-1）次大循环
  （2）每轮排序比力的次数逐轮淘汰
  （3）如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序
  （4）时间复杂度是O(N^2)      在有序的时间，很快，由于有exchange变量优化了代码
       
  1. #include<iostream>
  2. using namespace std;
  3. int a[20];
  4. void swap(int &a,int &b)
  5. {
  6.         int temp=a;
  7.         a=b;
  8.         b=temp;
  9. }
  11. void BubbleSort(int a[],int n)
  12. {
  13.         int i,j;
  14.         bool flag;
  15.         for(i=0;i<n-1;i++)
  16.         {
  17.                 flag=false;//每轮开始时初始化flag
  18.                 for( j=n-1;j>i;j--)//内层控制比较和交换
  19.                 {
  20.                         if(a[j-1]>a[j])
  21.                         {
  22.                                 swap(a[j-1],a[j]);
  23.                                 flag=true;
  24.                         }
  25.                 }
  26.                 if(flag==false)
  27.                 {
  28.                         break;
  29.                 }
  30.         }
  31. }
  33. int main()
  34. {
  35.        
  36.        
  37.         int n;
  38.         cout<<"请输入数组的大小"<<endl;
  39.         cin>>n;
  40.         for(int i=0;i<n;i++)
  41.         {
  42.                 cin>>a[i];
  43.         }
  44.         BubbleSort(a,n);
  45.         for(int i=0;i<n;i++)
  46.         {
  47.                 cout<<a[i]<<" ";
  48.         }
  49.         return 0;
  50. }
复制代码
2.快速排序
   
1.头脑：
          记第一个数为key，要调解key的位置，使得左边的都要比key的小，右边的数都比key的大。
  2.步调：
          选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
        照旧定义一个left和一个right，left从左向右走（当碰到大于key的值时停下来）。right从右向左走（当碰到小于key的值时停下来）。（若在最左边挖坑，则必要right先走；若在最右边挖坑，则必要left先走） 
          把right的那个小的数放在坑中，在把left那个位置的值放在right那个位置中
          重复操纵，直到left>right时结束，完成一趟，把key放在了精确的位置
          最后用分治头脑，分成左边和右边，递归。
  

  1. #include<iostream>
  2. using namespace std;
  4. int a[20];
  6. int parttition(int a[],int low,int high)
  7. {
  8.         int pivot=a[low];//那最左边的作为分割值
  9.         while(low<high)
  10.         {
  11.                 while(low<high&&a[high]>pivot)//从后往前遍历，找到一个比分割值小的
  12.                  high--;
  13.                  a[low]=a[high];
  14.             while(low<high&&a[low]<pivot)
  15.                  low++;
  16.              a[high]=a[low];
  17.         }
  18.         a[low]=pivot;
  19.         return low;
  20.        
  21. }
  22. void quicksort(int *a,int low,int high)
  23. {
  24.         if(low<high)
  25.         {
  26.                 int pivot_pos=parttition(a,low,high);
  27.                 quicksort(a,low,pivot_pos-1);
  28.                 quicksort(a,pivot_pos+1,high);
  29.         }
  30. }
  31. int main()
  32. {
  33.         int n;
  34.         cout<<" element have ";
  35.         cin>>n;
  36.         for(int i=0;i<n;i++)
  37.         {
  38.                 cin>>a[i];
  39.         }
  40.         quicksort(a,0,n-1) ;
  41.         for(int i=0;i<n;i++)
  42.         {
  43.                 cout<<a[i]<<" ";
  44.         }
  45.         return 0;
  46. }
复制代码

插入排序
   直接插入排序： 每次将一个记录按其关键字的大小插入到已经排好序的序列中，直至全部记录插入完毕。这种排序方式将待排数据依次和数组中已经排好序的记录进行比力并确定自己的位置。
  假设现在有 10 个元素的整型数组：int arr[] = {16, 1, 45, 23, 99, 2, 18, 67, 42, 10}，现在，我们希望对这个数组中的元素进行从小到大排序。
  根据直接插入排序算法的头脑，我们首先认为数组中的第 1 个元素（16）包罗在已经排好序的序列中。然后从数组中的第 2 个元素开始，依次针对数组中的元素寻找合适的位置插入到已经排好序的序列中就行了。
  以是，就会有下面的操纵步调：
  先看 1，1 比 16 小，以是 1 插入到 16 之前，16 后移。这是由于已经排好序的序列中目前只有 16，以是只必要将 16 后移，数组 arr 目前的情形是：{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。
接着看 45，45 比 1 和 16 都大以是 45 位置不动，数组 arr 目前的情形是：{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。
接着看 23，23 比 16 大但比 45 小，以是 23 插入到 45 之前，45 后移，数组 arr 目前的情形是：{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。
接着看 99，99 目前最大，以是位置不动，数组 arr 目前的情形是：{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。
接着看 2，2 比 1 大但比 16 小，以是 2 插入到 16 之前，16、23、45、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 23, 45, 99, 18, 67, 42, 10}。
接着看 18，18 比 16 大但比 23 小，以是 18 插入到 23 之前，23、45、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 45, 99, 67, 42, 10}。
接着看 67，67 比 45 大但比 99 小，以是 67 插入到 99 之前，99 后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 45, 67, 99, 42, 10}。
接着看 42，42 比 23 大但比 45 小，以是 42 插入到 45 之前，45、67、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 42, 45, 67, 99, 10}。
接着看 10，10 比 2 大但比 16 小，以是 10 插入到 16 之前，16、18、23、42、45、67、99 依次后移，数组 arr 目前的情形是：{1, 2, 10, 16, 18, 23, 42, 45, 67, 99}。
以上就是直接插入排序算法的完整工作过程形貌。
  把一个无序数组 {16, 1, 45, 23, 99, 2, 18, 67, 42, 10} 终极变得有序 {1, 2, 10, 16, 18, 23, 42, 45, 67, 99}，只必要从前向后遍历数组中的每个元素，再为每个元素找到合适的位置就可以了。
————————————————
    
  1. #include<iostream>
  2. using namespace std;
  3. int a[20];
  4. //直接插入排序
  6. void InsertSort(int arr[], int len) {
  7.         if (len <= 1) //不超过1个元素的数组，没必要排序
  8.                 return;
  9.        
  10.         for (int i = 1; i < len; i++) //从第2个元素（下标为1）开始比较
  11.         {
  12.                 if (arr[i] < arr[i - 1])
  13.                 {
  14.                         int  temp = arr[i]; //暂存arr[i]值，防止后续移动元素时值被覆盖   
  15.                         int j;
  16.                         //内层控制比较j要大于等于0，同时arr[j]大于temp时，arr[j] 位置元素向后覆盖
  17.                         for (j = i - 1; j >= 0 && arr[j] > temp; j--) //检查所有前面排好序的元素
  18.                         {
  19.                                 arr[j + 1] = arr[j]; //所有大于temp的元素都向后移动
  20.                         }
  21.                         arr[j + 1] = temp; //复制数据到插入位置，注意j因为被减了1，这里加回来
  22.                 }
  23.         }
  24.         return;
  25. }
  26. int main()
  27. {
  28.         int n;
  29.         cin>>n;
  30.         for(int i=0;i<n;i++)
  31.         {
  32.                 cin>>a[i];
  33.         }
  34.         InsertSort(a,n);
  35.         for(int i=0;i<n;i++){
  36.                 cout<<a[i]<<" ";
  37.         }
  38.         return 0;
  39.        
  40. }
复制代码
选择排序：简单选择排序  堆排序 数排序

选择排序

  1. //简单选择排序
  2. void SelectSort(int *a,int len)
  3. {
  4.         int i,j;
  5.         for( i=0;i<len-1;i++)//
  6.         {
  7.                 int min=i;
  8.                  
  9.                 for(j=i;j<len;j++)
  10.                 {
  11.                         if(a[j]<a[min])
  12.                         {
  13.                                 min=j;
  14.                         }
  15.                 }
  16.                 swap(a[i],a[min]);
  17.         }
  18. }
复制代码
堆排序：除了快排接着就是堆排序会在初试中出大题和选择题以是很重要
   假设我们有10个元素，将这十个元素建成一个完全二叉树这里采用层次建立法，我们将二叉树中的任意一个位置的元素对应到数组下标上，我们将二叉树中每个元素对应到数组下标的这种数据结构称为堆，好比最后一个父元素的下标是N/2-1,也就是a[4],还有如果父亲节点的下标是dad,那么父节点对应的左子节点的下标值是2*dad+1.接着将每颗子树都调解为父节点最大，终极将整棵树变为一个大根堆。变成大根堆之后，将第根节点和最后一个节点元素值交换，再接着调解成大根堆，直到最后。
  
  1. #include<iostream>
  2. using namespace std;
  3. int a[20];
  6. void swap(int &a,int &b)
  7. {
  8.         int temp=a;
  9.         a=b;
  10.         b=temp;
  11. }
  12. //直接插入排序
  14. void InsertSort(int arr[], int len) {
  15.         if (len <= 1) //不超过1个元素的数组，没必要排序
  16.                 return;
  17.        
  18.         for (int i = 1; i < len; i++) //从第2个元素（下标为1）开始比较
  19.         {
  20.                 if (arr[i] < arr[i - 1])
  21.                 {
  22.                         int  temp = arr[i]; //暂存arr[i]值，防止后续移动元素时值被覆盖   
  23.                         int j;
  24.                         //内层控制比较j要大于等于0，同时arr[j]大于temp时，arr[j] 位置元素向后覆盖
  25.                         for (j = i - 1; j >= 0 && arr[j] > temp; j--) //检查所有前面排好序的元素
  26.                         {
  27.                                 arr[j + 1] = arr[j]; //所有大于temp的元素都向后移动
  28.                         }
  29.                         arr[j + 1] = temp; //复制数据到插入位置，注意j因为被减了1，这里加回来
  30.                 }
  31.         }
  32.         return;
  33. }
  36. //简单选择排序
  38. void SelectSort(int* a, int n)
  39. {
  40.         for (int i = 0; i < n-1; i++)//i<n-1当它是最后一个数的时候不需要进行交换排序
  41.         {
  42.                 int min = i;//min记录最小元素的下标
  43.                 int j;
  44.                 for (j = i; j < n; j++)
  45.                 {
  46.                         if (a[j] < a[min])
  47.                         {
  48.                                 min=j;
  49.                         }
  50.                 }
  51.                 swap(a[i], a[min]);
  52.         }
  53. }
  54. //把某个子树调整为大根堆
  55. void AdjustDown(int *a,int k,int len)
  56. {
  57.         int dad=k;//父亲的下标
  58.         int son=2*k+1;//左孩子的下标
  59.         while(son<len)
  60.         {
  61.                 if(son+1<len&&a[son]<a[son+1])//如果左孩子小于右孩子
  62.                 {
  63.                         son++;//拿右孩子和dad比
  64.                 }
  65.                 if(a[son]>a[dad])
  66.                 {
  67.                         swap(a[son],a[dad]);   
  68.                         dad=son;//son重新作为dad，去判断下面的子树是否符合大根堆
  69.                         son=2*dad+1;
  70.                  }
  71.                  else
  72.                  {
  73.                          break;
  74.                  }
  75.          }
  76. }
  78. void HeapSort(int *a, int len)
  79. {
  80.         int i;
  81.         //就是把堆调整为大根堆  
  82.         for(i=len/2-1;i>=0;i--)
  83.         {
  84.                 AdjustDown(a,i,len);
  85.         }
  86.         swap(a[0],a[len-1]);//交换根部元素和最后一个元素
  87.         for(i=len-1;i>0;i--)
  88.         {
  89.                 AdjustDown(a,0,i);//调整剩余元素变为大根堆
  90.                 swap(a[0],a[i-1]); //交换根部元素和无序数组的最后一个元素
  91.          }
  92. }
  93. int main()
  94. {
  95.         int n;
  96.         cin>>n;
  97.         for(int i=0;i<n;i++)
  98.         {
  99.                 cin>>a[i];
  100.         }
  101.         //InsertSort(a,n);
  102.         //SelectSort(a,n);
  103.         HeapSort(a,n);
  104.         for(int i=0;i<n;i++){
  105.                 cout<<a[i]<<" ";
  106.         }
  107.         return 0;
  108.        
  109. }
复制代码
归并排序
   思路：
  1.不断的分割数据，让数据的每一段都有序（一个数据相当于有序）
  2.当所有子序列有序的时间，在把子序列归并，形成更大的子序列，终极整个数组有序。
  1. //归并排序
  2. void _MergeSort(int* a, int left, int right, int* tmp)//在这个函数中调用递归{
  3.         if (left >= right)
  4.         {
  5.                 return;
  6.         }
  7.         int mid = (left + right) >> 1;
  8.         _MergeSort(a, left, mid, tmp);
  9.         _MergeSort(a, mid+1, right, tmp);
  10.         //合并
  11.         int begin1 = left, end1 = mid;
  12.         int begin2 = mid + 1, end2 = right;
  13.         int i = left;
  14.         while (begin1 <= end1 && begin2 <= end2)
  15.         {
  16.                 if (a[begin1] <= a[begin2])
  17.                 {
  18.                         tmp[i++] = a[begin1++];
  19.                 }
  20.                 else
  21.                 {
  22.                         tmp[i++] = a[begin2++];
  23.                 }
  24.         }
  25.         while (begin1 <= end1)
  26.         {
  27.                 tmp[i++] = a[begin1++];
  28.         }
  29.         while (begin2 <= end2)
  30.         {
  31.                 tmp[i++] = a[begin2++];
  32.         }
  33.         for (int j = left; j <= right; j++)
  34.         {
  35.                 a[j] = tmp[j];
  36.         }
  37. }
  38. void MergeSort(int* a, int n)
  39. {
  40.         int* tmp = (int*)malloc(sizeof(int) * n);
  41.         _MergeSort(a, 0, n - 1, tmp);
  42.         free(tmp);
  43. }
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
继续阅读请点击广告
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

羊蹓狼

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

渠道 国产数据库 集成商 AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表