1.之前介绍的冒泡和选择排序都是适用于少量的数据，一旦数据量比较大，效率就很低的，因为他们的时间复杂度是o(n²）。
2.今天介绍一种算法不是很难，速度很快的排序算法，快速排序。
一 快速排序
1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归执行。
2）排序过程动图（来自百度百科）
3）步骤：
（1）设置两个变量 i，j,令i=0,j=n-1
(2) 选择一个元素作为分割点(key)，通常选第一个元素，令key=arrary[0]
(3) 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值a[j]，将a[j]和a[i]的值交换
(4) 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的a[i]，将a[i]和a[j]的值交换
(5) 重复第3、4步，直到i==j。此时排序完成
二 代码
我要评论 1 #include<stdio.h>
2 void quicksort(int *arr,int left,int right)
3 {
4 int i,j,temp;
5 i=left;
6 j=right;
7 if(i==j)//递归结束条件
8 return;
9 temp=arr[left];
10 while(j>i)
11 {
12 while(j>i&&arr[j]>=temp)
13 j--;
14 arr[i]=arr[j];
15 while(i<j&&arr[i]<=temp)
16 i++;
17 arr[j]=arr[i];
18 }
19 arr[j]=temp;
20 quicksort(arr,0,i);//递归执行，对左半分进行排序
21 quicksort(arr,i+1,right);//递归执行，对右半分进行排序
22 }
23 int main()
24 {
25 int i;
26 int arr[10]={1,3,-9,0,10,2,8,9,19,-1};
27 quicksort(arr,0,9);//选择排序
28 for(i=0;i<10;i++)
29 printf("%d\n",arr[i]);
30 return 0;
31 }
快速排序是冒泡排序的一种改进，的时间复杂度是o(nlog₂n)，是线性级。
如对本文有疑问， 点击进行留言回复！！
C语言字符数组应用示例1：编写一个程序，将两个字符串连接起来，不用strcat函数。
网友评论