之前我们跟随笔者重温了数据结构中的查询算法和部分排序算法，现在我们继续跟随笔者继续学习一些基本的排序算法。
选择排序
使用条件：可对比大小的集合。
算法思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}
-
- void SimpleSelect(int b[10])
- {
- int temp;
- int i;
- for(i=0;i<9;i++)
- {
- for(int j=i+1;j<9;j++)
- {
- if(b[i]>b[j])
- {
- temp=b[i];
- b[i]=b[j];
- b[j]=temp;
- }
- }
- }
- cout<<"the sort is:";
- for(int i=0;i<10;i++)
- {
- cout<<b[i]<<" ";
- }
- cout<<endl;
- }
|
性能分析：时间复杂度为O（n^2）
----------------------------------------------------------------------------------------------------
堆排序
使用条件：可对比大小的集合。
算法思想：其实堆排序是简单选择排序的一种进化，它最主要是减少比较的次数。什么是堆？若将序列对应看成一个完全二叉树，完全二叉树中所有非终端节点的值均不大于（或者不小于）其左右孩子节点的值，可以称作为堆。由堆的性质可以知道堆顶是一个最大关键字(或者最小关键字)。在输出堆顶后，使剩下的元素又建成一个堆，然后在输出对顶。如此反复执行，便能得到一个有序序列，这个过程成便是堆排序。
堆排序主要分为两个步骤：
1、从无序序列建堆。
2、输出对顶元素，在调成一个新堆。
举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}
-
- void HeapSort(int b[10])
- {
- void HeapAdjuest(int b[10],int min,int max);
- void Sawp(int *a,int *b);
- int i;
-
- for(i=9/2;i>=0;i--)
- {
- HeapAdjuest(b,i,9);
- }
-
- for(i=9;i>0;i--)
- {
- Sawp(&b[i],&b[0]);
- HeapAdjuest(b,0,i-1);
- }
- }
-
-
-
- void HeapAdjuest(int b[10],int min,int max)
- {
- if(max<=min)return ;
- int temp;
- temp=b[min];
- int j;
-
- for(j=2*min;j<=max;j*=2)
- {
-
- if(j<max&&b[j]<b[j+1])
- {
- j++;
- }
-
- if(temp>b[j])
- {
- break;
- }
-
- b[min]=b[j];
- min=j;
- }
- b[min]=temp;
- }
-
- void Sawp(int *a,int *b)
- {
- int temp;
- temp=*a;
- *a=*b;
- *b=temp;
- }
|
性能分析：时间复杂度时间复杂度O(nlogn)
