首页 > 代码库 > 快速排序
快速排序
快排思想:在数据序列中选择一个值作为key(基准)值,每趟从数据序列的两端开始交替进行,将小于key的元素交换到序列前端,将大于key的元素交换到序列后端,介于两者之间的位置则成为key的最终位置,同时,序列被划分为两个子序列,在用同样的方法分别对两个子序列进行排序,直到子序列的长度为1,则完成排序。
例 10 18 4 15 6 12 48 9
第一步: 令key=10,begin=0,end=7;序列从后到前查找比key的值小的元素,交换位置,然后 begin++;
此时序列: 9 18 4 15 6 12 48 10 key=10,begin=1 ,所对应的值为18;
第二步:序列以 begin开始从前往后查找比key值大的元素,交换位置,然后end--;
此时序列: 9 10 4 15 6 12 48 18 key=10, end=6,所对应的值为48;
.....直到满足begin>=end的时候结束第一次快排
第一次快排的结果为:9 6 4 10 15 12 48 18 此时begin=end=3;
具体代码如下:
public static void quickSort(int[] array, int begin, int end) { if (begin < end) { int temp = 0; int i = begin; int j = end; int key = array[i]; while (i != j) { while (i < j && key <= array[j]) { j--; } if (i < j) { temp = array[j]; array[j] = array[i]; array[i++] = temp; } while (i < j && key >= array[i]) { i++; } if (i < j) { temp = array[i]; array[i] = array[j]; array[j--] = temp; } } array[i] = key;//基准到达最终位置,从基准分成两部分 for (int a = 0; a <= array.length - 1; a++) System.out.print(array[a] + " "); System.out.println(" "); quickSort(array, begin, i - 1);//前半部分 quickSort(array, j + 1, end);//后半部分 } }
代码优化:取中间的数据作为基准key
public static void quicksort(int[] array, int begin, int end) { if (begin >= end) { return; } int key = array[(begin + end) / 2];//取中间值作为key int i = begin; int j = end; while (i <= j) { if (array[i] < key && i <= j) { i++; } if (array[j] > key && i <= j) { j--; } int temp = 0; temp = array[j]; array[j] = array[i]; array[i] = temp; i++; j--; } for (int a = 0; a < array.length; a++) { System.out.print(array[a] + " "); } quicksort(array, begin, j); quicksort(array, i, end); }
快排算法分析:
不稳定算法,最好情况空间复杂度为O(log2n),最坏情况O(n),平均空间复杂度为O(log2n),
当数据较大且数据序列随机排列时,适用快排,当数据较小,或key(基准)值选用不恰当时,快排较慢。
快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。