首页 > 代码库 > 快速排序（quicksort）
快速排序（quicksort）
快速排序是对冒泡排序算法的一种改进型算法，而且快速排序也采用了分治法的思想。快速排序是不稳定排序，
平均时间复杂度为：O(n*logn)，最坏时间复杂度为：O(n*n)，空间时间复杂度：O(logn)，但快速排序通常是用于排
序的最佳实用的选择。
快速排序的思想：从数组选取一个数（通常是第一个数）作为标准，从数组的高位开始查找，找到比作为标准数小的数
，然后进行交换，又从数组的低位开始查找，找到比作为标准大的数，然后进行交换，重复以上步骤，直至从高位到低位，
低位到高位重合为止。
示例：
6 3 8 7 2
第一次交换：2 3 8 7 6
第二次交换：2 3 6 7 8
第一遍排序完成，第二三就不详细说了。
示例代码：
#include <stdio.h>int Qsort(int array[], int low, int high) //进行排序{ int mark = array[low]; while(low<high) //判断是否重合 { while(low<high && array[high]>=mark) //从高位到低位查找小的数 high--; array[low] = array[high]; while(low<high && array[low]<=mark) //从低位到高位查找大的数 low++; array[high] = array[low]; } array[low] = mark; //将标记的数放到合适的位置 return low;}void QuickSort(int array[], int low, int high) //进行分解，采用分治法{ if(low<high) { int k = Qsort(array, low, high); QuickSort(array, low, k-1); QuickSort(array, k+1, high); }}int main(){ int n; int array[100]; printf("请输入数组的大小："); scanf("%d", &n); printf("请输入数组中的各个数："); for(int i = 0; i<n; i++) scanf("%d", &array[i]); QuickSort(array, 0, n-1); for(int i = 0; i<n; i++) printf("%d ", array[i]); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。