算法之——快速排序(Quick Sort)

2016-12-24 08:23:54来源:cnblogs.com作者:eudiwfe人点击

顾名思义,快速排序(quick sort)速度十分快,时间复杂度为O(nlogn)。虽然从此角度讲,也有很多排序算法如归并排序、堆排序甚至希尔排序等,都能达到如此快速,但是快速排序使用更加广泛,以至于STL中默认排序方法就是快速排序。此外,快速排序的思想——划分(Partition)思想给人很多启发。下面以非降序排序进行介绍,不求有更深的理解,只求为自己做个简要笔记。

1)划分(Partition)

划分思想十分简单,却又十分重要,应用广泛。即:将待排序数组以某一个元素为键值(Key),将比此key小的放在左边,否则放在右边。其可能的情况为:3,1,4,2,0,KEY=5,6,9,7,8.键值Key可以任意选择。好的键值对于提高性能有帮助,但选择最优键值的方法,本身就是一种排序思想。所以,对于排序来说,一般选择第一个元素作为Key。以下为Partition代码的一种实现:

注:此处end为数组长度N-1.

 1 int partition(int arr[],int start,int end){ 2     int i=start, j=end, key; 3     if (start>=end) return -1; 4     for(key=arr[i]; i<j;){ 5         for(;i<j && arr[j]>=key; --j); 6         arr[i] = arr[j]; 7         for(;i<j && arr[i]<=key; ++i); 8         arr[j] = arr[i]; 9     }10     arr[i] = key;11     return i;12 }

首先定义两个下标变量i,j,分别指向开始和结尾,并将开始start的元素作为键值key。然后从后向前遍历arr[],找到小于key的元素j,将其覆盖i;从前向后遍历arr[],找到大于key的元素i,将其覆盖j。直到i与j碰头,将key写回i。此时i的位置即选中的key应该在的位置,即:key左边的元素不大于key,key右边的不小于key。返回此时key的下标位置i。其时间复杂度为O(n).

2)快速排序(quick sort)

快速排序就是利用划分思想。每次经过划分之后,其key所在位置(下标)必然是经过排序后key所在的位置!如上面的3,1,4,2,0,KEY=5,6,9,7,8。元素5此时在位置5,正是其排序后的位置。再如:3,5,1,KEY=10,23,19.元素10在位置3,也是其排完序后所在的位置。正是如此,利用划分进行快速排序才成为可能。

快速排序思想为:对于数组arr[]以及其首位元素位置start和末尾元素end,选择其中一个元素作为Key,进行一趟划分,得到key此时应该在的位置i;然后对于key的左部分start~i-1进行划分,对于key右部分i+1~end进行划分;逐渐划分更小的范围进行划分。最终排序完毕。每次进二分划分,一共划分了logn次,故快速排序时间复杂度为O(nlogn)。

void quick_sort(int arr[],int start, int end){    int mid;    mid = partition(arr,start,end);    if (mid<0) return;    quick_sort(arr,0,mid-1);    quick_sort(arr,mid+1,end);}

一种写法更加巧妙的快速排序,将quick_sort与partition结合,如下:

 1 void quick_sort(int arr[],int start,int end){ 2     int i=start, j=end, key; 3     if (start>=end) return; 4     for(key=arr[i]; i<j;){ 5         for(;i<j && arr[j]>=key; --j); 6         arr[i] = arr[j]; 7         for(;i<j && arr[i]<=key; ++i); 8         arr[j] = arr[i]; 9     }10     arr[i] = key;11     quick_sort(arr,0,i-1);12     quick_sort(arr,i+1,end);13 }

注:以上end均为数组长度N-1.

对于长度为N的数组arr[]而言,快速排序只需调用quick_sort(arr,0,N-1)。

3)链表的快速排序

链表的排序方法也有很多,此处使用快速排序对单链表进行排序。其中链表节点定义如下:

1 typedef struct _ListNode{2     int val;3     struct _ListNode *next;4 }ListNode;

由于数组进行划分时,其元素进行移动很费时,然而对于链表而言,其元素划分后,并不需要移动,只需要指针交换即可。所以,定义两个指针mid和p,p进行快速向后遍历,当遇到小于KEY的节点时,将其加入到mid尾部并且mid后移一位。执行一趟partition后,p到达尾部NULL,mid为KEY的位置,然后继续划分start~mid以及mid~end。其代码如下:

 1 void qsort(ListNode *start,ListNode *end){ 2     if (start==end || start==NULL) return; 3     ListNode *p,*mid; 4     for(p=mid=start; p!=end; p=p->next){ 5         if(p->val > start->val) continue; 6         mid = mid->next; 7         swap(p->val,mid->val); 8     } 9     swap(start->val,mid->val);10     qsort(start,mid);11     qsort(mid->next,end);12 }

对于一个无头节点的单链表ListNode *head而言,进行快速排序只需调用qsort(head,NULL);即可。此处已将parition合并到快速排序中,并没有单独给出Partition,如需要请自行写出。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台