交换排序之快速排序（Quick Sort）

快速排序的介绍，包括快速排序的特点、原理和完整代码实现。

快速排序

快速排序是对冒泡排序算法的一种改进。

1、过程

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

2、特点

• 记录非顺次的移动导致排序方法是不稳定的
• 排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构
• 当n较大时，在平均情况下快速排序是所有内部排序算法中速度最快的一种，所以其适合初始记录无序、n较大时的情况

3、完整代码实现

#include<iostream>
#include<string>

using namespace std;
//将比轴心大的数据右移，比轴心小的数据左移，并返回轴心下标
int Calculate(int arr[], int start, int end)
{
    //获取轴心值
    int key = arr[start];
    while (start<end)
    {
        //轴心右边比轴心小的赋值给轴心下标，end末尾下标-1
        while (start<end&&arr[end]>=key)
        {
            --end;
        }
        arr[start] = arr[end];
        //轴心左边比轴心大的与轴心替换
        while (start<end && arr[start]<=key)
        {
            ++start;
        }
        arr[end] = arr[start];
    }
    arr[start] = key;//填充轴心值
    return start;
}

//快速排序
void QuickSort(int arr[], int start, int end)
{
    if (start<end)
    {
        int index = Calculate(arr,start,end);//获取轴心数据下标
        QuickSort(arr,start,index-1);//排序轴心左侧的数据
        QuickSort(arr,index+1,end);//排序轴心右侧的数据
    }
}

//数组打印
void printArr(int arr[], int len, int start = 0)
{
    cout << "{";
    for (int k = start; k < len; k++)
    {
        if (k == len - 1)
        {
            cout << arr[k] << " }";
        }
        else
        {
            cout << arr[k] << "，";
        }

    }
    cout << endl;
}

int main()
{
    int arr[8] = { 3,5,2,6,1,4,9,8 };
    int len = 8;
    QuickSort(arr, 0,len-1);    
    printArr(arr, len);
	system("pause");
	return 0;
}

快速排序动画演示