大家好,又见面了,我是你们的朋友全栈君。
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
2.1、设置两个变量 low、high,排序开始时:low=0,high=size-1。 2.2、整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面
2.3、第一趟找到的基准位置,作为下一趟的分界点。 2.4、递归调用(recursive)分界点前和分界点后的子数组排序,重复2.2、2.3、2.4的步骤。 2.5、最终就会得到排序好的数组。
三个函数 基准插入函数:int getStandard(int array[],int low,int high) (返回基准位置下标) 递归排序函数:void quickSort(int array[],int low,int high) 主函数:int main()
#include <stdio.h>
#include <stdlib.h>
void display(int* array, int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
int getStandard(int array[], int i, int j) {
// 基准数据
int key = array[i];
while (i < j) {
// 因为默认基准是从左边开始,所以从右边开始比较
// 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
while (i < j && array[j] >= key) {
j--;
}
// 当找到比 array[i] 小的时,就把后面的值 array[j] 赋给它
if (i < j) {
array[i] = array[j];
}
// 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
while (i < j && array[i] <= key) {
i++;
}
// 当找到比 array[j] 大的时,就把前面的值 array[i] 赋给它
if (i < j) {
array[j] = array[i];
}
}
// 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
// 把基准数据赋给正确位置
array[i] = key;
return i;
}
void QuickSort(int array[], int low, int high) {
// 开始默认基准为 low
if (low < high) {
// 分段位置下标
int standard = getStandard(array, low, high);
// 递归调用排序
// 左边排序
QuickSort(array, low, standard - 1);
// 右边排序
QuickSort(array, standard + 1, high);
}
}
// 合并到一起快速排序
// void QuickSort(int array[], int low, int high) {
// if (low < high) {
// int i = low;
// int j = high;
// int key = array[i];
// while (i < j) {
// while (i < j && array[j] >= key) {
// j--;
// }
// if (i < j) {
// array[i] = array[j];
// }
// while (i < j && array[i] <= key) {
// i++;
// }
// if (i < j) {
// array[j] = array[i];
// }
// }
// array[i] = key;
// QuickSort(array, low, i - 1);
// QuickSort(array, i + 1, high);
// }
// }
int main() {
int array[] = {
49, 38, 65, 97, 76, 13, 27, 49, 10};
int size = sizeof(array) / sizeof(int);
// 打印数据
printf("%d \n", size);
QuickSort(array, 0, size - 1);
display(array, size);
// int size = 20;
// int array[20] = {0}; // 数组初始化
// for (int i = 0; i < 10; i++) { // 数组个数
// for (int j = 0; j < size; j++) { // 数组大小
// array[j] = rand() % 1000; // 随机生成数大小 0~999
// }
// printf("原来的数组:");
// display(array, size);
// QuickSort(array, 0, size - 1);
// printf("排序后数组:");
// display(array, size);
// printf("\n");
// }
return 0;
}
(递归调用,不好展示每次排序结果)
时间复杂度:
空间复杂度: O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)
稳定性:不稳定
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/152562.html原文链接:https://javaforall.cn