/***************************************************
##filename : quicksort.c
##author : GYZ
##create time : 2018-10-31 09:54:39
##last modified : 2018-11-05 14:15:50
##description : NA
***************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void quickSort(int a[],int low,int high)
{
int i = low;
int j = high;
int temp = a[i];
/*判断递归是否结束*/
if(low < high)
{
/*循环相向而行,到两个下标值相等时,循环停止*/
while(i < j)
{
/*这个while将high -> j 中第一个小于temp的值给a[i]*/
while(a[j]>=temp && (i < j))
{
--j;
}
a[i] = a[j];
/*这个while将low -> i 中第一个大于temp的值给a[j]*/
while(a[i]<=temp && (i < j))
{
++i;
}
a[j] = a[i];
/*这两个while的结果就是以temp为比较值,大的分到右边,小的分到左边*/
}
a[i] = temp; /*上面的while之后,i(或者j)的位置,就是temp的位置,因为刚刚i左边是小于temp的值,右边是大于temp的值,所以i对应的就是temp*/
quickSort(a,low,i-1); /*进入左半部分进行比较,递归*/
quickSort(a,j+1,high); /*进入右半部分进行比较,递归*/
}
else
{
return ;
}
}
/*bubble sort*/
/*void bubbleInsert(int a[],int n)
{
int temp = 0;
int i = 0,j = 0;
for(i = 0; i < n; ++i)
{
for(j = i+1; j < n; ++j)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}*/
void printArr(int a[],int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d,",a[i]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int length = 0;
int begin,end;
int a[] = {26,20,10,14,15,21,22,23,24,25,28,29,30,3,5,6,1,9,4,8,2,7,11,13,12,27,18,19,16,17};
length = sizeof(a) / sizeof(a[0]);
begin = clock();
quickSort(a,0,length);
// bubbleInsert(a,length);
end = clock();
printf("%d\n",end-begin);
printArr(a,length);
return 0;
}