快速排序
快速排序是对冒泡排序的改进,主要思想是通过一次排序将序列分成两部分,左边的部分全部小于基准值,右边的部分大于基准值。在这一思想下,有不同的几种实现方式。
- 比较好理解的版本
/*
*quickSort
*这个版本是比较好理解的版本(效率不是最高的)
*quickSort函数第二个参数是要排序的数组起始下标,第三个参数是结束下标
*过程:
*1. 将最左边的数设为val(也即关键字)
*2. 从i开始向右找比val大的数,找到后停下
*3. 从j开始向左找比val小的数,找到后停下
*4. 如果i>=j则离开循环
*5. 否则:交换当前的两个数
*6. 对左边递归
*7. 对右边递归
*/
#include <stdio.h>
#include <time.h>
#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}
void quickSort(int *a, int left, int right);
int main(void)
{
int a[MAX] = {0};
int i;
srand(time(NULL));
printf("排序前:
");
for (i=0; i<MAX; i++)
{
a[i] = rand()%100;
printf("%d ", a[i]);
}
quickSort(a, 0, MAX-1);
printf("
排序后:
");
for (i=0; i<MAX; i++)
{
printf("%d ", a[i]);
}
printf("
");
return 0;
}
void quickSort(int *a, int left, int right)
{
if (left < right)
{
int i = left;
int j = right+1;
while (1)
{
while (i+1<MAX && a[++i]<a[left]);
while (j-1>-1 && a[--j]>a[left]);
if (i >= j)
{
break;
}
SWAP(a[i], a[j]);
}
SWAP(a[left], a[j]);
quickSort(a, left, j-1);
quickSort(a, j+1, right);
}
}
- 对于上述方法进行改进,将基准值设定为序列中间的数,从中间向两边寻找
/*
*从中间向两边查找,具体过程类似于容易理解的版本
*/
#include <stdio.h>
#include <time.h>
#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}
void quickSort(int *a, int left, int right);
int main(void)
{
int a[MAX] = {0};
int i;
srand(time(NULL));
printf("排序前:
");
for (i=0; i<MAX; i++)
{
a[i] = rand()%100;
printf("%d ", a[i]);
}
quickSort(a, 0, MAX-1);
printf("
排序后:
");
for (i=0; i<MAX; i++)
{
printf("%d ", a[i]);
}
printf("
");
return 0;
}
void quickSort(int *a, int left, int right)
{
if (left < right)
{
int t = a[(left+right)/2];
int i = left - 1;
int j = right + 1;
while (1)
{
while (a[++i] < t);
while (a[--j] > t);
if (i >= j)
{
break;
}
SWAP(a[i], a[j]);
}
quickSort(a, left, i-1);
quickSort(a, j+1, right);
}
}
-
再次改进算法。
有指针left和right,对于right,如果其所指的元素的值大于或者等于基准值,那么指针往左移一位,如果小于基准值,则和基准值交换;同理,对于left,如果left所指元素的值小于或者等于基准值,那么指针往右移一位,如果大于基准值,则和基准值交换。从right开始执行,重复这两步骤,直至left == right为止。
对于基准的选取会影响算法的性能,这里取第一个元素为pivot。
/*
*效率较高的实现
*/
#include <stdio.h>
#include <time.h>
#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}
void quickSort(int *a, int left, int right);
int Partition(int *a, int left, int right);
int main(void)
{
int a[MAX] = {0};
int i;
srand(time(NULL));
printf("排序前:
");
for (i=0; i<MAX; i++)
{
a[i] = rand()%100;
printf("%d ", a[i]);
}
quickSort(a, 0, MAX-1);
printf("
排序后:
");
for (i=0; i<MAX; i++)
{
printf("%d ", a[i]);
}
printf("
");
return 0;
}
int Partition(int *a, int left, int right)
{
int pivot = a[left];
while (left < right)
{
while (left < right && a[right] >= pivot)
{
--right;
}
a[left] = a[right];
while (left < right && a[left] <= pivot)
{
++left;
}
a[right] = a[left];
}
return left;
}
void quickSort(int *a, int left, int right)
{
int pivot;
if (left < right)
{
pivot = Partition(a, left, right);
quickSort(a, left, pivot-1);
quickSort(a, pivot+1, right);
}
}
来源:http://www.cnblogs.com/RootJie/archive/2012/02/13/2349649.html