Contents
  1. 1. 冒泡排序
  2. 2. 快速排序(不稳定)

昨天总结了插入排序,今天总结交换排序。
交换排序是一种主要以交换的方式对序列进行排序的方法。排序的基本方法或手段主要就是比较和交换,像选择法等都借助了交换的手段,但都不是主要以交换为手段,如在直接选择排序的时候,一轮比较就能确定最大元素的位置,最后再进行交换。交换排序被公认为“稳定”的排序方法。

冒泡排序

冒泡排序,是指计算机的一种排序方法,它的时间复杂度为O( n^2 ),虽然不及堆排序、快速排序的O(nlog n,底数为2),但是有两个优点:

  1. “编程复杂度”很低,很容易写出代码;
  2. 具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,而堆排序、快速排序均不具有稳定性。不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、快速排序。
    冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是
    最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
    由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。
    若记录序列的初始状态为”正序”,则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次比较,且不移动记录;反之,若记录序列的初始状态为”逆序”,则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

    快速排序(不稳定)

    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
C++,快速排续
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//C++,快速排序
void sort(int *a,int left,int right)
{
int i=left,j=right;
int k=a[left];
if(left>=right) return ;
while(i!=j)
{
while(i<j&& a[j]>=k) j--;
a[i]=a[j];
while(i<j&& a[i]<=k) i++;
a[j]=a[i];
}
a[i]=k;
sort(a,left,i-1);
sort(a,i+1,right);
}

下一节更新选择排序。

Contents
  1. 1. 冒泡排序
  2. 2. 快速排序(不稳定)