排序算法03------------快速排序

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)，是线性级。