快速排序的原理是通过一趟排序将待排记录分割成独立的两部分,一部分的关键字均比别一部分的关键字小,然后再分别对这两部分记录做快速排序,直到整个记录都有序为止。具体实现如下:
任意选取一个记录做为中枢key,将所有关键字小于中枢的排在它的前面,将所有关键字大于它的排在它的后面。另外使用两个指针low和high来记录,它们的初始值分别为待排记录的头和尾。首先从high所指位置起向前搜索一个小于中枢key的值,并与key的位置做交换。再从low开始向后搜索找到一个大于key的值,并与key的位置做交换。直到low与higt相等为止。
#include <stdio.h> #define SIZE (10) //快速排序 void quick_sort(int array[], int size) { //低指针从头开始 int low = 0; //高指针从尾开始 int high = size - 1; //本趟比较枢纽 int t = array[0]; //本趟结束条件 while (low < high) { //先从高指针向前找到小于枢纽的元素位置 while (low < high && array[high] >= t) { high--; } //与枢纽位置交换 array[low] = array[high]; //再从低指针向后找到大于枢纽的元素位置 while (low < high && array[low] <= t) { low++; } //与枢纽位置交换 array[high] = array[low]; } //当low和high相等时记录枢纽元素 array[low] = t; //计算前半段数组大小 int size_low = low; //计算后半段数组大小 int size_high = size - low - 1; if (size_low > 1) { //前半段递归快速排序 quick_sort(array, size_low); } if (size_high > 1) { //后半段递归快速排序 quick_sort(&array[low + 1], size_high); } } //显示数组 void display(int *array, int size) { for (int i = 0; i < size; i++) { printf("%d ", array[i]); } printf("\n"); } int main(int argc, char **args) { int array[SIZE] = { 5, 3, 7, 2, 9, 8, 1, 0, 6, 4 }; display(array, SIZE); quick_sort(array, SIZE); display(array, SIZE); return 0; }
运行结果:
5 3 7 2 9 8 1 0 6 4 0 1 2 3 4 5 6 7 8 9
本例代码:
code path chapter.08/e.g.8.4/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号