【数据结构】快速(QuickSort)排序之——前后指针法

ゝ一纸荒年。 2022-06-16 12:40 131阅读 0赞

快速排序的定义：

快速排序(Quick Sort)是一种有效的排序[算法][Link 1]。虽然[算法][Link 1]在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对[快速排序算法][Link 2]进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。

快速排序被认为是当前最优秀的内部排序方法。

前后指针算法的定义：

定义两个指针，prev和cur，再定义key的值，cur指针从left开始，遇到比key大的就过滤掉，比key小的，就停下来，prev++，判断prev和cur是否相等，如果不相等，就将两个值进行交换，最后一趟排序下来，比key小的，都留在了key的左边，比key大的都在key的右边。如下图所示：

![Center][]

完整的代码人如下：

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    int GetMidIndex(int *a, int left, int right)//三数取中法
    {
    	int mid = left + (right - left) / 2;
    	if (a[left] < a[mid])
    	{
    		if (a[left]>a[right])
    		{
    			return left;
    		}
    		else if (a[mid] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    	else
    	{
    		if (a[mid] > a[right])
    		{
    			return mid;
    		}
    		else if (a[left] > a[right])
    		{
    			return right;
    		}
    		else
    		{
    			return left;
    		}
    	}
    }
    
    int PartSort3(int *a, int left, int right)
    {
    	assert(a);
    	int mid = GetMidIndex(a, left, right);
    	swap(a[mid], a[right]);
    
    	int prev = left - 1;
    	int cur = left;
    	int key = a[right];
    	while (cur < right)
    	{
    		if (a[cur] < key && ++prev != cur)
    		{
    			swap(a[cur], a[prev]);
    		}
    		++cur;
    	}
    	swap(a[++prev], a[right]);
    	return prev;
    }
    
    void QuickSort(int *a, size_t left, size_t right)
    {
    	assert(a);
    	if (left >= right)
    	{
    		return;
    	}
    	int div = PartSort3(a, left, right);
    	QuickSort(a, left, div - 1);
    	QuickSort(a, div + 1, right);
    }
    
    void printArray(int *a, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	int arr[] = { 1, 3, 6, 0, 8, 2, 9, 4, 7, 5 };
    	/*int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };*/
    	int n = sizeof(arr) / sizeof(arr[0]);
    	cout << "进行快速排序后：";
    	QuickSort(arr, 0, n - 1);
    	printArray(arr, n);
    	system("pause");
    	return 0;
    }

进行排序后的结果如下：

![Center 1][]

[Link 1]: http://lib.csdn.net/base/datastructure
[Link 2]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=7638866
[Center]: /images/20220616/9e8c09f8c1fd47b8b65a59115736e527.png
[Center 1]: /images/20220616/6e96ec2ba0e04b6aafbb103b55ca1918.png