文章目录

• 1.快速排序简介
• 2.快速排序思路
• 3.快速排序演示
• 4.快速排序代码实现思路
• 5.快速排序代码

1.快速排序简介

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法。其具有在绝大多数情况下相当优异的性能

2.快速排序思路

1.首先,我们在数组中任取一数------通常称其为关键数据(key),通常会挑数组中最后或者第一个数据来作为key.2.而后我们设置两个变量i,j分别指代第一个数据与最后一个数据a[i],a[j],其中,j从最后的数据往前遍历,直到遇到第一个比key大的数据,而i从0开始遍历数组,直到遇到第一个比key小的数据为止,随后二者数据交换,然后再重复以上操作,最后即可将比key小的数据全部置于key前,而比key大的数据置于key后.

3.随后我们在前后区间内再重复以上操作,同样取分别取第一个数为key,同样分别在前后区间进行2的操作,最后我们便可得到有序的数据.

3.快速排序演示

假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。

此时，key=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。

此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。

此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，key成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

4.快速排序代码实现思路

首先,我们需要单独编写一个交换函数以方便交换操作

voidswap(int*x,int*y)
{
intt=*x;
*x=*y;
*y=t;
}

其次,我们可以利用循环执行比较与交换的操作.

而后运用递归执行两个前后区间中重复的操作.

5.快速排序代码

#include<stdio.h>voidswap(int*x,int*y)
{
intt=*x;
*x=*y;
*y=t;
}
voidQuickSort(int*a, intleft, intright)
{
if (left>=right)//如果区间只剩一个数或没有数就不进行操作return;
intkey=Sortonce(a, left, right);//调用排序函数，取key的位置QuickSort(a, left, key-1);//递归调用，对左区间进行排序QuickSort(a, key+1, right);//递归调用，对右区间进行排序}
intSortonce(int*a, intleft, intright)
{
intkey=left;//取最左边的元素做keywhile (left<right)//当左右没有相遇    {
while (left<right&&a[right] >=a[key])//如果右比key小就退出循环right--;
while (left<right&&a[left] <=a[key])//如果左比key大就退出循环left++;
swap(&a[left],&a[right]);//交换左右    }
swap(&a[key], &a[left]);//交换key和相遇位置的元素returnleft;//返回key的位置}
voidmain()
{
inti;
inta[] = {5,9,7,3,2,1,4,87,66,54,23,15,64,57,77,22,113};//测试案例QuickSort(a, 0, 17);
for (i=0; i<18; i++)
printf("%d\n",a[i]);
}