[算法]——快速排序(Quick Sort)

2018-06-18 04:11:21来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

1)划分(Partition)

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

// Partition - <small> KEY <big>
int partition(int arr[], int begin, int end)
{
	int i=begin, j=end-1, key;
	if (i>=j) return i;
	for (key=arr[i]; i<j;){
		// find last arr[j]<key
		for(; i<j && arr[j]>=key; --j);
		arr[i] = arr[j];
		// find first arr[i]>key
		for(; i<j && arr[i]<=key; ++i);
		arr[j] = arr[i];
	}
	arr[i] = key;
	return i;		// current key position
}	// Time O(n)
// after partition, the KEY must be the position where ordered

首先定义两个下标变量i,j,分别指向开始和结尾,并将开始begin的元素作为键值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[]以及其首位元素位置begin和末尾元素end,选择其中一个元素作为Key,进行一趟划分,得到key此时应该在的位置i;然后对于key的左部分begin~i-1进行划分,对于key右部分i+1~end进行划分;逐渐划分更小的范围进行划分。最终排序完毕。每次进二分划分,一共划分了logn次,故快速排序时间复杂度为O(nlogn)。

// quick sort, ascending order
void quick_sort(int arr[], int begin, int end)
{
	int mid = partition(arr,begin,end);
	if (mid<0) return;
	quick_sort(arr,begin,mid);
	quick_sort(arr,mid+1,end);
}

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

// A simple quick sort version, which combine partition and sort
void quick_sort(int arr[], int begin, int end)
{
    int i=begin, j=end-1, key;
    if (i>=j) return;
    for(key=arr[i]; i<j;){
        for(; i<j && arr[j]>=key; --j);
        arr[i] = arr[j];
        for(; i<j && arr[i]<=key; ++i);
        arr[j] = arr[i];
    }
    arr[i] = key;
    quick_sort(arr,begin,i);
    quick_sort(arr,i+1,end);
}

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

3)链表的快速排序

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

// A simple quick sort version, which combine partition and sort
// A simple ListNode define
typedef struct __ListNode
{
	int val;
	struct __ListNode *next;
}ListNode;

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

/*  quick sort - list version (ascending order)
 *  5 -> 3 -> 2 -> 7 -> 8 -> 1 -> 9 ->NULL
 *  |__begin: as KEY                   |__end
 *  |__mid  : as sorted list mid
 *
 *       p1   p2
 *  5 -> 3 -> 2 -> 7 -> 8 -> 1 -> 9 ->NULL
 *  |__begin
 *       |__mid (1)
 *            |__mid (2)
 *                 p3   p4
 *  5 -> 3 -> 2 -> 7 -> 8 -> 1 -> 9 ->NULL
 *  |__begin  |
 *            |__mid (2)
 *                           p5
 *  5 -> 3 -> 2 -> 7 -> 8 -> 1 -> 9 ->NULL
 *  |__begin  |
 *            |__mid (2): move mid, and swap(mid,p)
 *                           ||
 *                           p5
 *  5 -> 3 -> 2 -> 1 -> 8 -> 7 -> 9 ->NULL
 *  |__begin       |
 *                 |__mid (3)
 *
 *  at last, swap begin and mid:
 *  1 -> 3 -> 2 -> 5 -> 8 -> 7 -> 9 ->NULL
 *  |__begin       |
 *                 |__mid
 *  
 * */

其代码如下:

// quick sort by ascending order for list
void qsort(ListNode *begin, ListNode *end)
{
	if (begin==end || begin==NULL) return;
	ListNode *p, *mid;
	for(mid=begin, p=mid->next; p!=end; p=p->next){
		if (p->val > begin->val) continue;
		mid = mid->next;
		if (mid!=p) swap(p->val,mid->val);
	}
	swap(begin->val,mid->val);
	qsort(begin,mid);
	qsort(mid->next,end);
}

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

4) 第K小的数字(Kth-smallest number)

划分可以不用完全排序,就可以求一个数组中第k小(或第k大)的数字。

例如给定一个数组{5,2,3,1,4},求其第2小的数字。如果排序,则很容易找到其答案为2,但使用的时间为O(nlogn)。在划分时,如果当前返回的key的位置pos正是k,则可以直接找到答案,而不必完全排序。

// Kth-smallest number, partition by ascending order
int kth_smallest(int k, int arr[], int n) {
	int i=0, j=n, pos=-1;
	for(--k; pos!=k;){
		pos = partition(arr,i,j);
		i = (pos<k ? pos+1 : i);
		j = (pos>k ? pos : j);
	}
	return arr[k];
}

类似的题目可参见第k大元素。

注:本文涉及的源码:https://git.oschina.net/eudiwffe/codingstudy/blob/master/src/sort/quicksort.c

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c语言实现log日志的写入

下一篇:kd树和knn算法的c语言实现