南京大型门户网站制作/成都seo论坛

排序算法

这一部分主要介绍一些常用的基础排序算法，并从稳定性，时间、空间复杂度进行分析。

插入排序

插入排序将待排序的数据分成两个区域：有序区和无序区，每次将一个无序区中的数据按其大小插入到有序区中的适当位置，直到所有无序区中的数据都插入完成为止。

伪代码如下：

void insertsort(Elemtype a[], int n){int i, j;for(int i = 2; i<=n; i++){if(a[i] < a[i-1]){a[0] = a[i];for(int j = i-1; a[0] < a[j]; --j){a[j+1] = a[j];}a[j+1] = a[0];}}
}

分析：稳定性：稳定；时间复杂度：O($n^2$)；空间复杂度：O(1)。

冒泡排序

冒泡排序最多进行n-1趟排序，每趟排序时，按相同的方向扫描，一旦发现两个相邻的元素不符合规则，则交换。

伪代码如下：

void bubblesort(Elemtype a[], int n){for(int i = 0; i<n-1; i++){for(int j = 0; j<n-1-i; j++){if(a[j] < a[j+1]){swap(a[j], a[j+1]);}}}
}

分析：稳定性：稳定；时间复杂度：O($n^2$)；空间复杂度：O(1)。

改进方法：每趟排序时，记住最后一次发生交换的位置，则该位置之前的记录均已有序。

快速排序

在A[1,$\dots$,n]中任取一个数据元素作为比较的基准（记为X），将数据区划分为左右两个部分：A[1,$\dots$,i-1]和A[i+1,$\dots$,n]，且A[1,$\dots$,i-1] $\le$ X $\le$ A[i+1,$\dots$,n](1 $\le$ i $\le$ n)，当A[1,$\dots$,i-1]和A[i+1,$\dots$,n]非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。

伪代码如下：

int partition(Elemtype a[], int low, int high){Elemtype p = a[low];while(low < high){while(high>low && a[high]>=p) high--;a[low] = a[high];while(low<high && a[low]<=p) low++;a[high] = a[low];}a[low] = p;return low;
}void quicksort(Elemtype a[], int low, int high){if(low < high){int mid = partition(a, low, high);quicksort(a, low, mid-1);quicksort(a, mid+1, high);}
}

分析：稳定性：不稳定。

时间复杂度：每趟排序所需的比较次数为待排序区间的长度-1，排序趟数越多，占用时间越多。

最坏情况：每次划分选取的基准恰好都是当前序列中的最小(或最大)值，划分的结果A[low，$\dots$，i-1]为空区间 或A[i+1，$\dots$，high]是空区间，且非空区间长度达到最大值。这种情况下，必须进行n-1趟快速排序，第i次趟区间长度为n-i+1，总的比较次数达到最大值：n(n-1)/2 = O($n_2$)。

最好情况：每次划分所取的基准都是当前序列中的“中值”，划分后的两个新区间长度大致相等。共需lgn趟快速排序，总的关键字比较次数：O(n·lgn)。

平均情况：根据主定理可以得到，平均时间复杂度为O(n·lgn)。
基准的选择决定了算法性能。经常采用选取low和high之间一个随机位置作为基准的方式改善性能。

空间复杂度：快速排序在系统内部需要一个栈来实现递归，最坏情况下为O(n)，最佳情况下为O(lg·n)。

希尔（Shell）排序

希尔排序任取一个小于n的整数$S_1$作为增量，把所有元素分成 S 1 S_1 S