💎一站式轻松地调用各大LLM模型接口,支持GPT4、智谱、星火、月之暗面及文生图 广告
## 排序 本章先简单介绍了插入排序,然后着重讲述快速排序。 **插入排序** ~~~ // 版本1 void InsertSort(int a[], int n) { for(int i=1; i<n; ++i) for(int j=i; j>0 && a[j-1]>a[j]; --j) swap(a[j-1], a[j]); } // 版本2 void InsertSort1(int a[], int n) { for(int i=1; i<n; ++i) { int t = a[i]; int j = i; for(; j>0 && a[j-1]>t; --j) a[j] = a[j-1]; a[j] = t; } } ~~~ **快速排序** > > 我们在这里规定:小于等于pivot的元素移到左边,大于pivot的元素移到右边。 **实现1:单向移动版本** 这个版本的关键是设置一快一慢两个指针,慢指针左侧都是小于等于pivot(包含慢指针所在位置), 慢指针到快指针之间的值是大于pivot,快指针右侧的值是还未比较过的。示意图如下: ~~~ 小于等于pivot | 大于pivot | ? slow fast ~~~ 快指针一次一步向前走,遇到大于pivot什么也不做继续向前走。遇到小于等于pivot的元素, 则慢指针slow向前走一步,然后交换快慢指针指向的元素。一次划分结束后, 再递归对左右两侧的元素进行快排。代码如下: ~~~ // 数组快排 void QSort(int a[], int head, int end) { if(a==NULL || head==end) return; int slow = head, fast = head + 1; int pivot = a[head]; while(fast != end) { if(a[fast] <= pivot) swap(a[++slow], a[fast]); ++fast; } swap(a[head], a[slow]); QSort(a, head, slow); QSort(a, slow+1, end); } ~~~ 排序数组a只需要调用QSort(a, 0, n)即可。该思路同样可以很容易地在链表上实现: ~~~ // 单链表快排 void qsort(Node *head, Node *end){ if(head==NULL || head==end) return; Node *slow = head, *fast = head->next; int pivot = head->data; while(fast != end){ if(fast->data <= pivot){ slow = slow->next; swap(slow->data, fast->data); } fast = fast->next; } swap(head->data, slow->data); qsort(head, slow); qsort(slow->next, end); } ~~~ 排序头指针为head的单链表只需调用qsort(head, NULL)即可。 **实现2:双向移动版本** 版本1能能够快速完成对随机整数数组的排序,但如果数组有序, 或是数组中元素相同,快排的时间复杂度会退化成O(n2 ),性能变得非常差。 一种缓解方案是使用双向移动版本的快排,它每次划分也是使用两个指针, 不过一个是从左向右移动,一个是从右向左移动,示意图如下: ~~~ 小于等于pivot | ? | 大于pivot i j ~~~ 指针j不断向左移动,直到遇到小于等于pivot,就交换指针i和j所指元素 (指针i一开始指向pivot);指针i不断向右移动,直到遇到大于pivot的, 就交换指针i和j所指元素。pivot在这个过程中,不断地换来换去, 最终会停在分界线上,分界线左边都是小于等于它的元素,右边都是大于它的元素。 这样就避免了最后还要交换一次pivot的操作,代码也变得美观许多。 ~~~ int partition(int a[], int low, int high){ int pivot = a[low], i=low, j=high; while(i < j){ while(i<j && a[j]>pivot) --j; if(i < j) swap(a[i], a[j]); while(i<j && a[i]<=pivot) ++i; if(i < j) swap(a[i], a[j]); } return i; } void quicksort(int a[], int first, int last){ if(first<last){ int k = partition(a, first, last); quicksort(a, first, k-1); quicksort(a, k+1, last); } } ~~~ 当然,如果对于partition函数,你如果觉得大循环内的两个swap还是做了些无用功的话, 也可以把pivot的赋值放到最后一步,而不是在这个过程中swap来swap去的。代码如下: ~~~ int partition(int a[], int low, int high){ int pivot = a[low], i=low, j=high; while(i<j){ while(i<j && a[j]>pivot) --j; if(i<j) a[i++] = a[j]; while(i<j && a[i]<=pivot) ++i; if(i<j) a[j--] = a[i]; } a[i] = pivot; return i; } ~~~ 如果数组基本有序,那随机选择pivot(而不像上面那样选择第一个做为pivot) 会得到更好的性能。在partition函数里,我们只需要在数组中随机选一个元素, 然后将它和数组中第一个元素交换,后面的划分代码无需改变, 就可以达到随机选择pivot的效果。 **进一步优化** 对于小数组,用插入排序之类的简单方法来排序反而会更快,因此在快排中, 当数组长度小于某个值时,我们就什么也不做。对应到代码中, 就是修改quicksort中的if条件: ~~~ if(first < last) 改为 if(last-first > cutoff) ~~~ 其中cutoff是一个小整数。程序结束时,数组并不是有序的, 而是被组合成一块一块随机排列的值,并且满足这样的条件: 某一块中的元素小于它右边任何块中的元素。我们必须通过另一种排序算法对块内进行排序。 由于数组是几乎有序的,因此插入排序比较适用。 这种方法结合了快排和插入排序,让它们去做各自擅长的事情,往往比单纯用快排要快。 深入阅读:Don Knuth的《The Art of Computer Programming, Volume 3: Sorting and Searching》;Robert Sedgewick的《Algorithms》; 《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。