首页 > 代码库 > 快速排序及C语言实现
快速排序及C语言实现
快速排序算法最坏复杂度很差,相当于插入排序,但是平均性能很好,甚至大多数时候优于堆排序和归并排序,并且是一种内排序算法,因此在实际中往往用的最多。
快速排序的步骤:将数组a[p...r]划分为两个子数组a[p...q-1]和a[q+1...r],使得前者的每个元素小于等于a[q],后者的每个元素大于等于a[q]。然后再递归调用函数,对这两个子数组进行快速排序即可。
#include <stdio.h> void quicksort(int *a,int p,int r); int partition(int *a,int p,int r); main() { int a[12] = {2,8,23,7,1,3,5,34,64,6,32,4}; int i; //printf("%d\n",partition(a,1,8)); quicksort(a,1,12); for (i = 0;i < 12;i++) printf("%d ",a[i]); printf("\n"); } void quicksort(int *a,int p,int r) { int q;//,partition(int *a,int p,int r); if (p < r) { q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } int partition(int *a,int p,int r) { int x,i,j; int temp; x = a[r-1]; i = p - 1; for (j = p-1;j < r-1;j++) { if (a[j] <= x) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; } } temp = a[i]; a[i] = a[r-1]; a[r-1] = temp; return i+1; }
快速排序及C语言实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。