2、快速排序

一、概念及其介绍

　　快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

二、该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数（哨兵）。
• 2．分区过程，里面有2个循环，第一个循环是从右边开始找比这个基准值小的值，找到后交换，第二个循环是从左边开始找   找到比这个基准值大的值，然后交换。
• 3．再对左、右区间（第一次循环结束后，基准值的左边就是左区间，基准值的右边就是右区间）重复第二步，直到各区间只有一个数。 

 二、代码：

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>


using namespace std;

int sort(int *data,int left,int right)
{
    if (left >= right) return 0;

    int i = left;            //i开始为left的值，排序时索引值不断往右走，当i和j,相同时，基准值就找到了正确位置
    int j = right;            //j开始为right的值，排序时索引值不断往左走，当i和j,相同时，基准值就找到了正确位置
    int key = data[left];        //第一个值为基准值

    while (i < j)
    {
        while (i < j && key < data[j])      
        {
            j--;        
        }
        data[i] = data[j];    //从右边开始找，找到右边的值大于等于基准值时，跳出，然后把右边小的值放的前面来
    
        while (i < j && key >= data[i])
        {
            i++;
        }
        data[j] = data[i];
    }
    //i==j
    data[i] = key;            //把基准值放的正确的位置

    sort(data, left, i - 1);   //基准值左区间递归
    sort(data, i + 1, right);    //基准值右区间递归

    return 0;
}

int quick_sort(int *data,int length)
{
    sort(data, 0, length - 1);
    return 0;
}


int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = { 23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97 };
    quick_sort(data, sizeof(data) / sizeof(int));

    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        printf("%4d", data[i]);
    }

    system("pause");
    return 0;
}