- //讨论用各种方法对数据进行排序
- #include<iostream>
- using namespace std;
- //1.插入排序
- //1.1直接插入排序 基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。
- //时间复杂度:最好O(n),平均和最坏O(n^2)
- //空间复杂度:
- void InsSort(int a[],int n)
- {
- int i,j,k;
- for (i=1;i<n;i++)
- {
- for(j=i-1;j>=0;j--)
- {
- if(a[i]>=a[j])//为a[i]找合适的位置。
- break;
- }
- if (j != i - 1) //如找到了一个合适的位置。
- { //如果j=i-1,则不用移动。
- //将比a[i]大的数据向后移
- int temp = a[i];
- for (k = i - 1; k > j; k--)
- a[k + 1] = a[k];
- //将a[i]放到正确位置上
- a[k + 1] = temp;
- }
- }
- }
- //1.2希尔排序 基本思想:按增量d划分为若干组,再对每组用直接增量法进行排序。
- //时间复杂度:O(nlog n) 空间复杂度:O(1)
- void ShellSort(int a[],int n)
- {
- int d, i, j, temp;
- for(d=n/2;d>0;d/=2) //设定步长d.
- {
- for(i=d;i<n;++i) //在元素间移动为止
- for(j=i-d;j>=0&&a[j]>a[j+d];j-=d) //j=i-d只是初始条件。比较相距d的元素,逆序互换
- {
- temp=a[j]; //后面元素比前面元素大时需要交换。
- a[j]=a[j+d];
- a[j+d]=temp;
- }
- }
- }
- //2.交换排序
- //2.1冒泡排序 基本思想:对n个记录的序列,进行n-1次扫描。每次扫描时,都从小到大对相邻的两个关键字进行比较,第一次扫描把最大者置尾,第二次次大者……
- //如果不符合由小到大的顺序,就交换他们的位置。
- //时间复杂度: 最好O(n),最坏O(n^2),平均O(O^2) 空间复杂度:O(1)
- void BubbleSort(int a[],int n)
- {
- int i,j,temp;
- for(i=1;i<n;i++)//对序列进行n-1次扫描。
- {
- for(j=0;j<n-i;j++)//减少循环次数。
- {
- if(a[j]>a[j+1])
- {
- temp=a[j];
- a[j]=a[j+1];
- a[j+1]=temp;
- }
- }
- }
- }
- //2.2快速排序 基本思想是:先从数列中取出一个数作为基准数。
- //分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
- //再对左右区间重复第二步,直到各区间只有一个数。
- //时间复杂度:最坏O(n^2),平均O(nlog2N) 空间复杂度:nlog
- void QuickSort(int a[],int t,int n)
- { //挖坑填数
- int x=a[t];//将a[t]作为基准。
- int i=t,j=n-1,l;
- while(i<j)
- {
- while(i<j&&a[j]>=x)//从数组的最右面开始,找出比x小的元素去填坑。
- j--;
- if(i<j)
- {
- a[i]=a[j];
- i++;//a[j]放入a[i]中后,a[j]就形成了一个坑。
- }
- while(i<j&&a[i]<x)//从数组的最左面开始,找出比x大的数。
- i++;
- if(i<j)
- {
- a[j]=a[i];//a[i]形成了一个坑。
- j--;
- }
- //退出循环是i=j;
- a[i]=x;//将基准放入坑。
- //接下来分而治之
- l=i;
- QuickSort(a,0,l-1);
- QuickSort(a,l+1,n);
- }
- }
- void main()
- {
- int a[19]={2,1,7,5,4,7,3,1,8,46,43,34,45,57,12,8,5,4,3};
- /*InsSort(a,19);*/
- /*ShellSort(a,19);*/
- /*BubbleSort(a,19);*/
- QuickSort(a,0,19);
- for(int i=0;i<19;i++)
- cout<<a[i]<<'\\t';
- }
- //该片段来自于http://www.codesnippet.cn/detail/2808201410361.html
来源: http://www.codesnippet.cn/detail/2808201410361.html