快排C语言实现
- 快排的主要思想就是把一组数分成两组，左边那一组的最大数都比右边的最小数小，然后再对左边那一组数进行相同操作，再对右边的数进行相同操作。直到这一组数变成一个数单独成组，排序完成。
比如 3 5 9 -8 5 4
- 在第一次分组时变成 第一组{-8} 标准值3 第二组{5 9 5 4} 这里标准值就使该组的第一个数，此时第一组的所有数小于标准值小于第二组的所有数。那么再对第一组和第二组的所有数进行相同操作则排序成功。代码如下：
第一种
void sort(int * a, int len) {
if(len <= 1) return; //数组长度等于一或者等于零的时候，不必排序
//a为每一组的第一个元素的地址，len为每一组的长度
int i=0. j=len-1, temp=a[0];//初始化i指向数组开头，初始化j指向数组结尾，temp为标准值
while(i<j) {//只要i，j不相遇，就一直扫描
while(a[j] > temp) j--;
a[i] = a[j];
//后面的数只要大于前面的数就不管，往前扫描，直到小于或等于标准值的时候，把a[j]赋值给前面的a[i]
//注意，此时a[j]有两份而a[i]原来的值被覆盖，且a[j]是没有用的，因为它小于标准值，它应该在前面a[i]的位置
while(a[i] <= temp) i++;
a[j] = a[i];
//前面的数小于等于标准值就继续扫描
//注意此时在上面的那一份多余a[j]被替换掉了，但是多了一份a[i]，它大于标准值，它应该此刻j对应的位置.
//这个循环又会走到上面消去这个无用的a[i]。
}
//执行完上面这个循环，在i的位置上会多一个无用的a[i]，因为最后一次多余的a[i]不会被替换掉
//而且可以发现在进入循环时，无端消去了一个并不是多余的a[i]，因为是第一次的时候，所以是a[0]。
//而temp=a[0]，并且可以发现a[i]前面的数必定小于temp，a[i]后面的数必定大于temp,所以可以令a[i] = temp，这样数组的元素就没有变化，并且完成了把数分成两组;
a[i] = temp;
//对前一组，后一组 数分别继续进行这种操作
sort(a, i);//0~i-1长度为i
sort(a+i+1, len-i-1);
return;
}
void sort(int * a, int len) {
if( len <= 1 ) return;
int i=0, j=len-1, temp = a[0], t;
while( i<j ) {
while( a[j]>temp && j>i ) j--;
while( a[i]<=temp && i<j ) i++;
if(i != j) { //i等于j时交换没有意义,否则使小数到前面，大数到后面
t = a[i];
a[i]=a[j];
a[j]=t;
}
}
//由于是先从后面往前扫描，所以无论何时，从后往前扫描停止时，当时的a[j]必定不大于temp,则退出时a[i]必定不大于temp
//使标准值到中间形成 小数数组 标准值 大数数组
a[0]=a[i];
a[i]=temp;
sort(a, i);
sort(a+i+1, len-i-1);
return;
}
#include<stdio.h>
void sort(int * a, int len) {
if( len <= 1 ) return;
int i=0, j=len-1, temp = a[0];
while( i<j ) {
while( a[j]>temp && j>i ) j--;
a[i] = a[j];
while( a[i]<=temp && i<j ) i++;
a[j] = a[i];
}
a[i] = temp;
sort(a, i);
sort(a+i+1, len-i-1);
return;
}
int main(void) {
int i, a[13] = {-100, 4, 6, -10, 9, 46, -4, 3, 6, 5, 8, 44, 20};
sort(a, 13);
for(i=0; i<13; i++) {
printf("%d ", a[i]);
}
return 0;
}
