排序算法总结.docx

文档介绍：排序算法总结
“yuanc”为你分享19篇“
排序算法总结
”，经本站小编整理后发布，但愿对你的工作、学习、生活带来方便。
篇1：选择排序算法总结
这里实现了选择数组里面最小值的代码，读者可以以此类推自己写出选择最大值的算法
/实现
/** * 找到数组里面第k大的元素 * ***@param array 输入的数组 * ***@param arraysize 数组大小 * ***@param kthnumber 第k大元素的大小 * ***@param k 第k大的元素 */void randomizedselect(int array[] , int arraysize , int * kthnumber , int k){ if(array == null || arraysize <= 0 || kthnumber == null || k <0 || k >= arraysize) return; randomizedselectkernel(array, 0 , arraysize-1 , kthnumber , k);}/** * 找到leftborder到rightborder中第k大的元素,递归函数 * ***@param array 输入的数组 * ***@param leftborder 左边界 * ***@param rightborder 右边界 * ***@param kthnumber 第k大的元素的实际值 * ***@param k 第k大的元素 */void randomizedselectkernel(int array[], int leftborder , int rightborder ,int * kthnumber , int k){ if(leftborder > rightborder) return ; // 这里采用快速排序的思想来完成 int i = leftborder-1; int j = leftborder; int x = array[rightborder]; // 首先找到主元 for(; j < rightborder ; ++j) { if(array[j] <= x) {exchange(array , j , ++i); } } ++i; exchange(array , i , rightborder); // 现在位置i就是需要放置主元的地方 if(i == leftborder+k-1) *kthnumber = array[i]; else if(i > leftborder+k-1) randomizedselectkernel(array , leftborder , i-1 , kthnumber , k); else if(i < leftborder+k-1) randomizedselectkernel(array , i+1, rightborder , kthnumber , k-(i-leftborder+1));}
运行结果
input array is :
96 47 95 38 53 45 3 92 20 73
2th max number is———————- 20
3 20 45 38 47 53 73 92 96 95
1th max number is———————- 3
3 20 45 38 47 53 73 92 96 95
3th max number is———————- 38
3 20 38 45 47 53 73 92 96 95
6th max number is———————- 53
3 20 38 45 47 53 73 92 96 95
迭代方式实现
/** * 找到数组里面第k大的元素 * ***@param array 输入的数组 * ***@param arraysize 数组大小 * ***@param kthnumber 第k大元素的大小 * ***@param k 第k大的元素 */void randomizedselect(int array[] , int arraysize , int * kthnumber , int k){ if(array == null || arraysize <= 0 || kthnumber == null || k <0 || k >= arraysize) return; int left = 0; int right = arraysize-1; int k