交换排序：快速排序（不稳定的排序）
快速排序（Quick Sort）是一种常见的排序算法，它采用分治法的思想，对待排序序列进行划分，使得划分出的子序列可以分别进行排序，最终使整个序列有序。快速排序的最好情况下的时间复杂度为：O(nlogn)，最坏时间复杂度：O(n^2)，是一种高效的排序算法。快速排序是所有内部排序算法中平均性能最优的排序算法
快速排序的具体实现：
- 选择一个基准元素，一般选择第一个元素作为基准元素；
- 将序列分为两部分，一部分是所有比基准元素小的元素，另一部分是所有比基准元素大的元素；
- 对两个子序列进行递归排序，直到子序列长度为1，排序完成。
代码如下
int part(int arr[], int low, int high)
{
int pivot = arr[low];//将当前表中的第一个元素设为枢轴，对表进行划分
while (low < high)//循环跳出条件
{
while (low < high && arr[high] >= pivot)
--high;
arr[low] = arr[high];//将比枢轴小的元素移动到左端
while (low < high && arr[low] <= pivot)
++low;
arr[high] = arr[low];//将比枢轴大的元素移动到右端
}
arr[low] = pivot;//枢轴元素存放到最终位置
return low;//返回存放枢轴的最终位置
}
void quicksort(int arr[], int low, int high)
{
if (low < high)
{
int pivot = part(arr, low, high);
quicksort(arr, low, pivot-1);//依次对两个子表进行递归排序
quicksort(arr, pivot+1, high);
}
}完整测试代码
#include<stdio.h>
int part(int arr[], int low, int high)
{
int pivot = arr[low];//将当前表中的第一个元素设为枢轴，对表进行划分
while (low < high)//循环跳出条件
{
while (low < high && arr[high] >= pivot)
--high;
arr[low] = arr[high];//将比枢轴小的元素移动到左端
while (low < high && arr[low] <= pivot)
++low;
arr[high] = arr[low];//将比枢轴大的元素移动到右端
}
arr[low] = pivot;//枢轴元素存放到最终位置
return low;//返回存放枢轴的最终位置
}
void quicksort(int arr[], int low, int high)
{
if (low < high)
{
int pivot = part(arr, low, high);
quicksort(arr, low, pivot-1);//依次对两个子表进行递归排序
quicksort(arr, pivot+1, high);
}
}
int main()
{
int i = 0;
int arr[7] = { 49,38,65,98,76,13,27 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("原始数组为：");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
quicksort(arr, 0, sz - 1);
printf("\n快速排序之后的数组为：");
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
