【数据结构】快速(QuickSort)排序之——挖坑法

古城微笑少年丶 2022-06-16 12:19 235阅读 0赞

快速排序的定义：

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

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

挖坑法的定义：

有一个数组a\[size\],左指针left指向下标为0的位置，右指针right指向下标为size-1的位置，同时标志key=a\[right\];首先将key的位置设为一个坑，从left开始，找比key值大的，找到后将a\[left\]放到坑里，即a\[right\]=a\[left\]，同时将left的位置再设为坑;再从right开始找比key小的，找到后将a\[right\]放到上次设的坑里，即a\[left\]= a\[right\];直到left>=right,将key值放到现在的坑中即可。此时的数组呈现出左边的值都比key值小，右边的值都比key值大。一次快排将数组分为两个区间，我们再对每个区间进行上述的排序方式。直到每个小区间已不能再划分。

![Center][]

代码实现如下：

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    int PartSort2(int *a, int left, int right)
    {
    	int key = a[right];//坑
    	while (left < right)
    	{
    		while (left < right && a[left] <= key)
    		{
    			++left;
    
    		}
    		
    		a[right] = a[left];
    
    		while (left < right && a[right] >= key)
    		{
    			--right;
    
    		}
    		
    		a[left] = a[right];
    	}
    	a[left] = key;
    	return left;
    }
    
    void QuickSort(int *a, int left, int right)
    {
    	assert(a);
    	if (left >= right)
    	{
    		return;
    	}
    	int div = PartSort2(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, 0, 7, 8, 2, 9, 4, 6, 5 };
    
    	/*int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };*/
    	int n = sizeof(arr) / sizeof(arr[0]);
    	cout << "进行快速排序前：";
    	printArray(arr, n);
    	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/19b01fe6b4f2448ba21729e8612961e7.png
[Center 1]: /images/20220616/f09d0eb50cb048778241924f07abf11f.png