常见的排序算法
排序算法
交换类排序法
- 交换排序法 是指借助数据元素之间互相交换进行的排序算法。
冒泡排序 BubbleSort
基本概念：
依次比较相邻的两个数，将小数放在前面，大数放在后面。
- 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。
- 在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
- 如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
实现：
外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，…，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,…,9，对于每一个i,j的值依次为1,2,…10-i。
初始数据 ： 116 103 105 120 114
一次排序 ： 103 116 105 114 120
|<->| |<->|
二次排序 ： 103 105 116 114 120
|<->|
三次排序 ： 103 105 114 116 120
|<->|
四次排序 ： 103 105 114 116 120
C 实现：
void Bublesort(int a[],int n)
{
int i,j,k;
for(j=0;j<n;j++) /* 气泡法要排序n次*/
{
for(i=0;i<n-j;i++) /* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
{
if(a[i]>a[i+1]) /* 把值比较大的元素沉到底 */
{
k=a[i];
a[i]=a[i+1];
a[i+1]=k;
}
}
}
}
性能分析
若记录序列的初始状态为”正序”，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为”逆序”，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
快速排序 QuickSort
基本思想：
快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
例子
如无序数组[6 2 4 1 5 9]
a),先把第一项[6]取出来, 用[6]依次与其余项进行比较, 如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边 如果比[6]大就放[6]后边,9比[6]大,放到[6]后边 一趟排完后变成下边这样: 排序前 6 2 4 1 5 9 排序后 2 4 1 5 6 9
b),对前半拉[2 4 1 5]继续进行快速排序 重复步骤a)后变成下边这样: 排序前 2 4 1 5 排序后 1 2 4 5 前半拉排序完成,总的排序也完成: 排序前:[6 2 4 1 5 9] 排序后:[1 2 4 5 6 9]
C实现
#include <iostream>
using namespace std;
void printa(int a[],int low,int high)
{
for(int i=low;i<high+1;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
cout<<"----end----"<<endl;
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
cout<<"----before----"<<endl;
printa(a,low,high);
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
cout<<"----start-----"<<endl;
printa(a,low,high);
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
cout<<"----start2-----"<<endl;
printa(a,low,high);
/*将比第一个大的移到高端*/
}
a[first] = key;
cout<<"----oneend-----"<<endl;
printa(a,low,high);
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {3,4,1,3,5,6,7,3,2,7,9,8};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/
实际运行
----before----
3 4 1 3 5 6 7 3 2 7 9 8
----start-----
2 4 1 3 5 6 7 3 2 7 9 8
----start2-----
2 4 1 3 5 6 7 3 4 7 9 8
----start-----
2 1 1 3 5 6 7 3 4 7 9 8
----start2-----
2 1 1 3 5 6 7 3 4 7 9 8
----oneend-----
2 1 3 3 5 6 7 3 4 7 9 8
----before----
2 1
----start-----
1 1
----start2-----
1 1
----oneend-----
1 2
----end----
----end----
----before----
3 5 6 7 3 4 7 9 8
----start-----
3 5 6 7 3 4 7 9 8
----start2-----
3 5 6 7 3 4 7 9 8
----oneend-----
3 5 6 7 3 4 7 9 8
----end----
----before----
5 6 7 3 4 7 9 8
----start-----
4 6 7 3 4 7 9 8
----start2-----
4 6 7 3 6 7 9 8
----start-----
4 3 7 3 6 7 9 8
----start2-----
4 3 7 7 6 7 9 8
----start-----
4 3 7 7 6 7 9 8
----start2-----
4 3 7 7 6 7 9 8
----oneend-----
4 3 5 7 6 7 9 8
----before----
4 3
----start-----
3 3
----start2-----
3 3
----oneend-----
3 4
----end----
----end----
----before----
7 6 7 9 8
----start-----
6 6 7 9 8
----start2-----
6 6 7 9 8
----oneend-----
6 7 7 9 8
----end----
----before----
7 9 8
----start-----
7 9 8
----start2-----
7 9 8
----oneend-----
7 9 8
----end----
----before----
9 8
----start-----
8 8
----start2-----
8 8
----oneend-----
8 9
----end----
----end----
123334567789请按任意键继续. . .
性能分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)
的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
在最好情况下，每次划分所取的基准都是当前无序区的”中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。