数据结构--快速排序

曾经终败给现在 2022-07-28 11:47 140阅读 0赞

快速排序是一种平均性能比较好的排序方法，它的平均性能是Ο(nlogn)。快速排序的算法思想是：

1、选取待排序记录中的一项作为qvoit，即枢轴，以此作为基准，首先将待排序序列分为两类，一类是比排序序列大的，在基准的右边。一类是比基准小的，在基准的左边，当然这里排序的出发点是从左到右非递减序列。

2、对左边序列重复步骤一的过程；即递归调用函数；

3、对右边序列重复步骤一的过程；即递归表用；

下面以一组序列作为讲解：

![20160415142145902][]

说明：  
1、首先index代表数组的下标，value对应该下标下的值

2、选取4作为基准，然后开始筛选。low从-1开始递增，high从7开始递减，分别与基准4作比较。找到待排序序列中比基准数字小的第一个分点以及比基准数字大的第一个分点，在例中即下标为1和下标5的点。因此在这里将9和3进行互换，得到上图的第一个结果：2 3 1 7 5 9 8 4；

3、继续进行2的步骤。low从2开始，high从5开始，最后找到下一个分点，此时high=1,low=2,由于low>high,因此第一次重排结束。

4、将右边序列的第一个数字和4进行交换，得到了第一次以4为基准的结果，即：2 3 1 4 5 9 8 7

5、对左边序列2 3 1 和右边序列5 9 8 6进行递归，重复1 2 3 4过程。

![20160415144122285][]

最后的实现代码如下：

#include<iostream>
    using namespace std;
    
    template<class T>
    void QuickSort(T *sort_array, int left, int right)
    {
    	/**
    	index |-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|
    	value   2   9   1   7   5   3   8   4
    	    |                               |
    		low                            high
        first time:
    	    low=2;high=5; ----> index |-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|
    	                        value   2   3   1   7   5   9   8   4
    	                                    |               |
    		                               low            high
    	    low=3;high=2; ----> index |-0-|-1-|-2-|-3-|-4-|-5-|-6-|-7-|
    	                        value   2   3   1   7   5   9   8   4
    	                                        |   |
    		                                  high  low
    	   the first time result: 2 3 1 4 5 9 8 7
    
    	Then:
    			分别递归4的左边和右边
    	左边：
    	index |-0-|-1-|-2-|            index   |-4-|-5-|-6-|-7-|
    	value   2   3   1              value     5   9   8   7
    	|               |                |                   |
    	low            high              low                high
    	*/
    
    	int low = left-1;
    	int high = right;
    	int qvoit = sort_array[right];
    
    	if (left < right)
    	{
    
    		do
    		{
    			do { low++;  } while (sort_array[low] < qvoit);
    			do { high--; } while (sort_array[high] > qvoit);
    			if (low<high)
    			swap(sort_array[low],sort_array[high]);
    		} while (low < high);
    		swap(sort_array[right], sort_array[low]);
    
    		QuickSort(sort_array, left, low-1);
    		QuickSort(sort_array, low+1, right);
    	}
    
    
    
    }
    
    int main(int argc, char* argv[])
    {
    	int sort_array[8] = { 2, 9, 1, 7, 5, 3, 8, 4 };
    	QuickSort(sort_array, 0, 7);
    	for (int i = 0; i < 8; i++)
    	{
    		cout << sort_array[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }

[20160415142145902]: /images/20220724/f42c5f87384847ad8a8223d530f5cc7b.png
[20160415144122285]: /images/20220724/9910542282254a7187034a72892e06f9.png