By

文章目录

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

快速排序由于效率在同为 O(NlogN) O(NlogN) O(NlogN)O(NlogN) 的几种排序方法中效率较高，因此经常 的几种排序方法中效率较高，因此经常 的几种排序方法中效率较高，因此经常 被采用，再加上快速排序思想 被采用，再加上快速排序思想 —— 分治法也确实 非常 实用 ，因此很多软件公司的 笔试 面，包括像腾讯微软等知名 IT 公司都喜欢考这个， 公司都喜欢考这个， 还有大小的程序 方面的考试如软，研中 也常出现快速排序的身影 。
总的说来，要直接默写出快速排序还是有一定难度因 总的说来，要直接默写出快速排序还是有一定难度。

快速排序是 C.R.A.HoareC.R.A.Hoare C.R.A.Hoare C.R.A.Hoare C.R.A.HoareC.R.A.Hoare于 1962 年提出的一种划分 交换排序。它采用了治的策略，通 常称其为分治法 (Divide (Divide (Divide -andand -ConquerMethod)ConquerMethod) ConquerMethod) ConquerMethod) 。
该方法的基本思想是：

1．先从数列中取出一个作为基准。

2．分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等分区过程，将比这个数大的全放到它 右边小于或等的左边。

3．再对左右区间重复第二步，直到各只有一个数。

虽然快速排序称为分治法，但这三个字显无很好的概括全 虽然快速排序称为分治法，但这三个字显无很好的概括全 部步骤。因此我的对快速排序作了进一说明 ：挖坑填数 +分治法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
int Partition(int a[], int left, int right) {  
    int base = a[left];  
    while (left < right) {  
        while (left < right && a[right]>base) //从右往左找出第一个比基准小的数据  
            --right;  
        a[left] = a[right]; //将这个数放到基准的左边  
        while (left < right && a[left]<base) //从左往右找出第一个比基准大的数据  
            ++left;  
        a[right] = a[left]; //放到右边  
    }  
    a[left] = base;  
    return left; //返回基准的位置  
}  
void  QuickSort(int a[], int left, int right) {  
    int i;  
    if (left < right) {  
        i = Partition(a, left, right);  
        QuickSort(a, left, i-1);  
        QuickSort(a, i+1, right);  
    }  
}  
void main()
{
	int n = 10;
	int a[10] = { 72,6,57,88,60,42,83,73,48,85};
	QuickSort(a,0,n-1);
	for(int j = 0; j < n; ++j)
	{
		cout << a[j] << "   ";
	}
}

文章目录