C语言-排序算法——快速排序
快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
排序过程及示意图
代码如下
方法1
void quick_sort(int x[], int low, int high)//快速排序,后面满足条件的往前面丢,前面满足条件的往后面丢
{
int i, j, key;//变量key是用来保存当前参考元素的值
if (low < high)//判断高低位标记是否重合
{
key = x[low];//key默认保存第一个元素的值
i = low;//用i代替最低下标low做运算
j = high;//用j代替最高下标high做运算
while (i < j)//判断高低位标记是否重合
{
//从数组后半部分向前比较,找到小于参考元素值的位置,直到标记i和j重合
while (i < j&&x[j] >= key)
j--;
if (i < j)
x[i++] = x[j];//数组后半部分的较小元素往前丢
//从数组前半部分向后比较,找到大于参考元素值的位置,直到标记i和j重合
while (i < j&&x[i] <= key)
i++;
if (i < j)
x[j--] = x[i];//数组前半部分的较大元素往后丢
}
x[i] = key;//参考元素放回数组中
//把整个数组划分为两半部分,前半部分的元素总是比后半部分小
quick_sort(x, low, i - 1);//前半部分递归排序
quick_sort(x, i + 1, high);//后半部分递归排序
}
}
int main()
{
int a[N] = { 34, 66, 123, 34, 89, 1234, 678, 0, 42, 6 };
quick_sort(a, 0, 9);
for (int i = 0; i < N; i++)
{
printf("%d\t", a[i]);
}
printf("\n");
printf("\n");
system("pause");
return 0;
}
方法2:
void Swap(int v[], int a, int b)
{
int temp = v[a];
v[a] = v[b];
v[b] = temp;
}
void quick_sort(int v[], int left, int right)
{
//快排是分治法的体现 首先从中间找一个基准 进行一遍扫描 比基准小的放左边 比基准大的放右边 然后进行一个递归
int i, last;
if (left >= right)
return;
Swap(v, left, (left + right) / 2);
last = left;//last就是基准
for (i = left + 1; i <= right; i++)
if (v[i] < v[left])
Swap(v, ++last, i);
Swap(v, left, last);//基准数换回来
quick_sort(v, left, last - 1);
quick_sort(v, last + 1, right);
}
int main()
{
int a[N] = { 34, 66, 123, 34, 89, 1234, 678, 0, 42, 6 };
quick_sort(a, 0, 9);
for (int i = 0; i < N; i++)
{
printf("%d\t", a[i]);
}
printf("\n");
printf("\n");
system("pause");
return 0;
}
时间复杂度
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(n2)