排序算法详解快速排序

文章目录

一、什么是快速排序

   快速排序算法，简称快排，是最实用的排序算法，各大语言标准库的排序函数也基本都是基于快排实现的。快速排序是对冒泡排序算法的一种改进，同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，这种思路就叫做分治法。

二、过程详解

首先快排我们需要一个起始下标和末尾下标并记录其中一个元素。

int i = start, j = end, temp = arr[i];

然后我们在对 j 所对应的元素与temp进行比较，如果大于temp则 j--，否则的话将其与 i 所对应的元素进行交换并且 i++，然后再对 i 所对应的元素与temp进行比较，如果小于temp则 i++，否则的话将其与 j 所对应的元素进行交换并且 j--。一直到 i 与 j 重合再将temp赋予 i 所对应的元素，此时temp元素左边就全是小于它的元素，而右边就全是大于他的元素。

while (i<j)
    {
        while (i<j&&arr[j] >= temp)
        {
            j--;
        }
        if (i < j)
            arr[i++] = arr[j];
        while (i < j&&arr[i] <= temp)
        {
            i++;
        }
        if (i < j)
            arr[j--] = arr[i];
    }
    arr[i] = temp;

最后在对其左右两边进行递归就可完成排序。

总代码如下：

//快速排序
void QuickSort (int *arr, int start, int end)
{
    if (start >= end)    //如果不满足则直接返回
        return;
    int i = start, j = end, temp = arr[i];    //保存起始下标 末尾下标 起始元素
    while (i < j)    //i与j未重合
    {
        while (i < j && arr[j] >= temp)   
        {
            j--;
        }
        if (i < j)
            arr[i++] = arr[j];
        while (i < j && arr[i] <= temp)
        {
            i++;
        }
        if (i < j)
            arr[j--] = arr[i];
    }
    arr[i] = temp;
    QuickSort(arr, start, i - 1);
    QuickSort(arr, i + 1, end);
}
//检验
int main() 
{
    int n[10] = { 3, 5, 8, 4, 1, 6, 9, 2, 0, 7 };
    QuickSort(n, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        cout << n[i] << endl;
    }
    return 0;
}
//最后输出结果为：0，1，2，3，4，5，6，7，8，9

总结

   排序算法是为了让无序的数据组合变成有序的数据组合。 有序的数据组合最大的优势是在于当你进行数据定位和采用时， 会非常方便，因为这个数据是有序的 从而在代码设计的时候会让你避免很多不必要的麻烦， 因为无序数据你在进行推断数据前后关系的时候会显示很繁琐 快速排序是排序中的一种，它在最差情况下和别的排序相差不大 而在最优，一般情况下，会比一般的排序方法更节省时间。