C语言实现快速排序算法
|
一、快速排序算法（Quicksort） 1. 定义 快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。
2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 3. 步骤 a. 先从数列中取出一个数作为基准数。 b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 c. 再对左右区间重复第二步，直到各区间只有一个数。 二、C语言实现代码（仅供参考） /***************************************************** File name：Quicksort Author：Zhengqijun Version:1.0 Date: 2016/11/04 Description: 对数组进行快速排序 Funcion List: 实现快速排序算法 *****************************************************/ #include #include #define BUF_SIZE 10 /************************************************** *函数名：display *作用：打印数组元素 *参数：array - 打印的数组，maxlen - 数组元素个数 *返回值：无 **************************************************/ void display(int array[],int maxlen) { int i; for(i = 0; i < maxlen; i++) { printf("%-3d",array[i]); } printf("n"); return ; } /******************************** *函数名：swap *作用：交换两个数的值 *参数：交换的两个数 *返回值：无 ********************************/ void swap(int *a,int *b) { int temp; temp = *a; *a = *b; *b = temp; return ; } /************************************ *函数名：quicksort *作用：快速排序算法 *参数： *返回值：无 ************************************/ void quicksort(int array[],int maxlen,int begin,int end) { int i,j; if(begin < end) { i = begin + 1; // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！ j = end; // array[end]是数组的最后一位 while(i < j) { if(array[i] > array[begin]) // 如果比较的数组元素大于基准数，则交换位置。 { swap(&array[i],&array[j]); // 交换两个数 j--; } else { i++; // 将数组向后移一位，继续与基准数比较。 } } /* 跳出while循环后，i = j。 * 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin] * --> array[i+1] ~ array[end] > array[begin] * 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。 * 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！ */ if(array[i] >= array[begin]) // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！ { i--; } swap(&array[begin],&array[i]); // 交换array[i]与array[begin] quicksort(array,maxlen,begin,i); quicksort(array,j,end); } } // 主函数 int main() { int n; int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61}; int maxlen = BUF_SIZE; printf("排序前的数组n"); display(array,maxlen); quicksort(array,maxlen-1); // 快速排序 printf("排序后的数组n"); display(array,maxlen); return 0; } 执行程序后的结果如下所示：
上诉代码结合了我自己对快速排序的看法和理解，仅供参考。 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程之家。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
