内部排序——交换排序

这篇文章接着上一篇文章写，想要知道完整内部排序可以看一看上一篇文章。

2.交换排序

交换排序分为：冒泡排序，快速排序（非常快）

• 冒泡排序

大家学 C 语言的时候都学过冒泡排序，这个和它是一样的。简单回忆一下如何冒泡排序吧！

一组数中，把最大的数放在最后面，不断循环，直到排序完成。（类似于鱼吐泡泡）举一个列子，

49 65 23 98 34 78 用冒泡排序

49 65 23 34 78 98

49 23 34 65 78 98

23 34 49 65 78 98。 这样冒泡就完成啦！

• 快速排序

快速排序的基本思想是把当前待排序的记录，存放到整个表排好序后，它应当在的最终位置上。将原来的待排序表分割成两部分，其中一部分表中的关键字均比另一部分表中的关键字小。然后，分别对两部分表用同样的的方式进行排序，直到整个表排好序。

算法

int Partition( SqList &L, int low, int high){

pivotkey =L.r[low].key; //(pivotkey 是辅助空间)

while (low< high ) {

while(low <high && L.r[high].key>=piotkey)--high;

L.r[low] <-> L.r[high];

while (low<high&&L.r[low].key<=pivotkey) ++low;

L.r[low] <->L.r[high];

}

L.r[low]= pivotkey;

return low;

}// Partition

Void QSort (SqList &L, int low, int high) {

if ( low< high) {

picotloc =Partition(L,low,high);

QSort(L,low,pivotloc-1);

QSort(L, pivotloc+1 high);

}//QSort

Void QuickSort(SqList &L){

Qsort(L,1,L.length);

}//QuickSort

总结

冒泡排序相对简单，但时间复杂度相比于快速排序慢很多。快速排序是最好的内排序，但它不稳定。