八大排序算法-快速排序

ゝ一世哀愁。 2022-06-07 10:55 209阅读 0赞

快速排序算法的定义是：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法的基本思想：

设要排序的[数组][Link 1]是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的[排序算法][Link 2]，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1）设置两个变量i、j，[排序][Link 3]开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给**key**，即**key**=A\[0\]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于**key**的值A\[j\]，将A\[j\]和A\[i\]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于**key**的A\[i\]，将A\[i\]和A\[j\]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A\[j\]不小于**key**,4中A\[i\]不大于**key**的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

时间复杂度：O(nlogn)。

算法：

#include "stdafx.h"
    #include "stdafx.h"
    #include "iostream"
    
    int arr[] = { 35, 28, 58, 10, 61, 58, 97, 17 };
    int k = sizeof(arr) / sizeof(arr[0]);
    
    void quickSort(int a[], int low, int high)
    {
    	if (low >= high)
    	{
    		return;
    	}
    	int first = low;
    	int last = high;
    	int key = a[first];/*用字表的第一个记录作为枢轴*/
    
    	while (first < last)
    	{
    		while (first < last && a[last] >= key)
    		{
    			--last;
    		}
    
    		a[first] = a[last];/*将比第一个小的移到低端*/
    
    		while (first < last && a[first] <= key)
    		{
    			++first;
    		}
    
    		a[last] = a[first];
    		/*将比第一个大的移到高端*/
    	}
    	a[first] = key;/*枢轴记录到位*/
    	quickSort(a, low, first - 1);
    	quickSort(a, first + 1, high);
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	quickSort(arr, 0, k - 1);
    
    	for (int f = 0; f < k; f++)
    	{
    		std::cout << arr[f] << "  ";
    	}
    
    	getchar();
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84
[Link 2]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[Link 3]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F