时间:2021-05-20
一、快速排序算法(Quicksort)
1. 定义
快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。
2. 基本思想
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3. 步骤
a. 先从数列中取出一个数作为基准数。
b. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
c. 再对左右区间重复第二步,直到各区间只有一个数。
二、C语言实现代码(仅供参考)
/*****************************************************File name:QuicksortAuthor:Zhengqijun Version:1.0 Date: 2016/11/04Description: 对数组进行快速排序Funcion List: 实现快速排序算法*****************************************************/ #include <stdio.h>#include <stdlib.h> #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, maxlen, 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, 0, maxlen-1); // 快速排序 printf("排序后的数组\n"); display(array, maxlen); return 0;}执行程序后的结果如下所示:
上诉代码结合了我自己对快速排序的看法和理解,仅供参考。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C语言实现归并排序算法归并排序(Mergesort)是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型
本文实例讲述了基于C语言实现的迷宫算法。分享给大家供大家参考,具体如下:利用c语言实现迷宫算法,环境是vc++6.0.#include#include#incl
本文实例为大家分享了C语言实现24点游戏的具体代码,供大家参考,具体内容如下参考文章:C语言实现经典24点算法将算法实现改成C语言,并可在linux服务器上运行
调用C语言的快速排序算法qsort();?12345678910111213141516171819202122232425262728293031323334
C语言数据结构算法之实现快速傅立叶变换本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作、复数的基本掾作,复习所学过的动态内存分配、