【数据结构】快速排序
发布时间:2020-12-15 05:54:07 所属栏目:安全 来源:网络整理
导读:参考维基百科: 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 步骤为: 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基
参考维基百科: 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 步骤为:
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。 ? 参考博客: http://www.voidcn.com/article/p-mwmpzcut-pc.html ? 下面给出代码实现: #include <stdio.h> void Swap(int *a,int *b) { int temp; temp = *a; *a = *b; *b = temp; } // 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素 int Partition(int array[],int low,int high) { // 采用子序列的第一个元素为枢纽元素 int pivot = array[low]; while (low < high) { // 从后往前在后半部分中寻找第一个小于枢纽元素的元素 while (low < high && array[high] >= pivot) { --high; } // 将这个比枢纽元素小的元素交换到前半部分 Swap(&array[low],&array[high]); // 从前往后在前半部分中寻找第一个大于枢纽元素的元素 while (low < high && array[low] <= pivot) { ++low; } // 将这个比枢纽元素大的元素交换到后半部分 Swap(&array[low],&array[high]); } // 返回枢纽元素所在的位置 return low; } // 快速排序 void QuickSort(int array[],int high) { if (low < high) { int n = Partition(array,low,high); QuickSort(array,n); QuickSort(array,n + 1,high); } } void Qsort(int array[],int n) { QuickSort(array,n-1); } int main() { int i; int a[]={23,4,9,34,12,3,89,7,80}; Qsort(a,9); for(i=0; i<9; i++) printf("%d ",a[i]); printf("n"); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |