快排图示.jpg
快速排序之所比较快，因为相比冒泡排序，每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。
快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，
平均时间复杂度为O(NlogN)。
快速排序是基于“二分”的思想。
C语言代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MaxLen 10
void printArray(int arr[],int length)
{
for (int i = 0; i<length; i++) {
printf(" %d",arr[i]);
}
printf("\n");
}
void quickSort(int arr[],int left,int right)
{
static int count;
int i,j,temp;
if (left<right)
{
i = left;
j = right;
temp = arr[i];
count ++;
printf("\n第%d轮，left=%d,right=%d,temp=%d\n",count,left,right,temp);
while (i<j)
{
while (i<j&&arr[j]>temp)
{
j--;
}
if (i<j)
{
arr[i] = arr[j];
i++;
}
printArray(arr, MaxLen);
while (i<j&&arr[i]<temp)
{
i++;
}
if (i<j)
{
arr[j] = arr[i];
}
printArray(arr, MaxLen);
}
arr[i] = temp;
printArray(arr, MaxLen);
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
else
{
return;
}
}
int main(int argc, const char * argv[]) {
int arr[MaxLen] ;
srand( (unsigned)time( NULL ) );
for (int i = 0; i<MaxLen; i++)
{
arr[i] = rand()%50+1;
}
printf("原始数组：\n");
printArray(arr, MaxLen);
quickSort(arr, 0, MaxLen-1);
printf("快排后数组：\n");
printArray(arr, MaxLen);
return 0;
}
运行结果
原始数组：
46 3 11 39 37 24 24 11 13 20
第1轮，left=0,right=9,temp=46
20 3 11 39 37 24 24 11 13 20
20 3 11 39 37 24 24 11 13 20
20 3 11 39 37 24 24 11 13 46
第2轮，left=0,right=8,temp=20
13 3 11 39 37 24 24 11 13 46
13 3 11 39 37 24 24 11 39 46
13 3 11 11 37 24 24 11 39 46
13 3 11 11 37 24 24 37 39 46
13 3 11 11 37 24 24 37 39 46
13 3 11 11 37 24 24 37 39 46
13 3 11 11 20 24 24 37 39 46
第3轮，left=0,right=3,temp=13
11 3 11 11 20 24 24 37 39 46
11 3 11 11 20 24 24 37 39 46
11 3 11 13 20 24 24 37 39 46
第4轮，left=0,right=2,temp=11
11 3 11 13 20 24 24 37 39 46
11 3 11 13 20 24 24 37 39 46
11 3 11 13 20 24 24 37 39 46
第5轮，left=0,right=1,temp=11
3 3 11 13 20 24 24 37 39 46
3 3 11 13 20 24 24 37 39 46
3 11 11 13 20 24 24 37 39 46
第6轮，left=5,right=8,temp=24
3 11 11 13 20 24 24 37 39 46
3 11 11 13 20 24 24 37 39 46
3 11 11 13 20 24 24 37 39 46
第7轮，left=7,right=8,temp=37
3 11 11 13 20 24 24 37 39 46
3 11 11 13 20 24 24 37 39 46
3 11 11 13 20 24 24 37 39 46
快排后数组：
3 11 11 13 20 24 24 37 39 46
Program ended with exit code: 0
