交换排序
冒泡排序
算法描述
每一趟比较过程中，将第一个与第二个、第二个与第三个、……第n-1个与第n个分别比较，逆序就交换。如果某一趟过程中没有发生交换，则排序完毕。
算法实现
void BubbleSort(SqList &L) {
m = L.length - 1; flag = 1;
while((m > 0) && (flag == 1)) {
flag = 0;
for(j = 1; j <= m; j++)
if(L.r[j].key > L.r[j + 1].key) {
flag = 1;
t = L.r[j]; L.r[j] = L.r[j + 1]; L.r[j + 1] = t;
}
m--;
}
}
算法分析
- 时间复杂度
最好（初始正序）：一趟 n-1次关键字比较 不移动
最坏（初始逆序）：n-1趟
平均时间复杂度O(n²) - 空间复杂度
交换过程中需要一个暂存辅助，复杂度为O(1)
算法特点
- 稳定排序。
- 可以用于链式结构。
- 初始无序且元素较多时效率低。
快速排序
算法描述
任意（一般是第一个）取一个元素作为基准点，将基准点放在序列中间，将序列分为左右两个序列。设置左右两个指针，初始时指向表的下界和上界。右指针从右往左搜索，找到第一个比基准小的元素，移到左指针指向的位置；然后左指针从左往右搜索，找到第一个比基准大的元素，移到右指针指向的位置；一直重复，直到左右指针指向同一位置。
整体来看就是基准点把待排序序列分成左右两个子表，然后对于任何一个表都有一个基准点和左右子表，所有小于基准点的都放在他左边，大于基准点的都放在他右边。
算法实现
int Partition(SqList &L, int low, int high) {
L.r[0] = L.r[low]; // 基准点移动
pivotkey = L.r[low].key;
while(low < high) {
while(low < high && L.[high].key >= pivotkey) high--;
L.r[low] = L.r[high];
while(low < high && L.r[low].key <= pivotkey) low++;
L.r[high] = L.r[low];
} // 一次排序
L.r[low] = L.r[0]; // 基准点复位
return low;
}
void QSort(SqList &L, int low, int high) {
if(low < high) {
pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivtloc + 1, high); // 左右子表分别递归
}
}
void QuickSort(SqList &L) {
QSort(L, 1, L.length);
}
算法分析
- 时间复杂度
最好（初始正序）：一趟 n-1次关键字比较 不移动
最坏（初始已经排号）：递归树为单支树，需要n-1趟
平均时间复杂度O(n²) - 空间复杂度
交换过程中需要一个暂存辅助，复杂度为O(1)
算法特点
- 不稳定排序。
- 不适用于链式结构。
- 平均情况下是内部排序中最快的（以空间换时间），适用于初始记录无序、n较大。