Java经典排序算法-快速排序

基本思想
1.在待排序的元素任取一个元素作为基准(通常选第一个元素),称为基准元素;
2.将待排序的元素进行分区,比基准元素大的元素放在它的右边,比其小的放在它的左边;
3.对左右两个分区重复以上步骤直到所有元素都是有序的。

排序方法
首先我们要明确每一轮的排序目的:用基准数将数组以左侧值小于基准数,右侧值大于基准数隔开。

定义一个基准数k(取数组首位),定义最低位i(数组最低下标),定义最高位j(数组最高下标)。先从右往左查比k小的值(即j- -),再从左往右查比k大的值(即i++),交换双方位置。再次执行上述步骤,直至ij重合,此时将k值与ij的值交换(归位),完成第一轮排序。将k值左侧部分和k值右侧部分按照以上步骤再次排序,直至数组顺序为止。

  1. public static void main(String[] args) {
  2. // TODO Auto-generated method stub
  3. int[] array = {6,1,2,7,9,3,4,5,10,8};
  4. System.out.println("排序前:"+Arrays.toString(array));
  5. quickSort(array,0,array.length-1);
  6. System.out.println("排序后:"+Arrays.toString(array));
  7. }
  8. /**
  9. * 快速排序
  10. * @param array 待排数组
  11. * @param low 最低位
  12. * @param high 最高位
  13. */
  14. public static void quickSort(int[] array,int low,int high){
  15. //递归终止条件
  16. if(low > high){
  17. return;
  18. }
  19. int k = array[low];//基准值,一般取数组开头或结尾
  20. int i = low;//最低位,负责找出比k大的数
  21. int j = high;//最高位,负责找出比k小的数
  22. int temp = 0;//临时储存变量
  23. //最低位与最高位重合则结束循环
  24. while(i < j){
  25. //当找到比k小的值时结束循环
  26. while(array[j] >= k && i < j){
  27. j--;//往数组低位移动
  28. }
  29. //当找到比k大的值时结束循环
  30. while(array[i] <= k && i < j){
  31. i++;//往数组高位移动
  32. }
  33. //交换位置
  34. if(i < j){
  35. temp = array[i];
  36. array[i] = array[j];
  37. array[j] = temp;
  38. }
  39. }
  40. //重合位与基准位交换
  41. array[low] = array[i];
  42. array[i] = k;
  43. //基准位左侧快速排序
  44. quickSort(array, low, i-1);
  45. //基准位右侧快速排序
  46. quickSort(array, i+1, high);
  47. }

代码执行结果

  1. 排序前:[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
  2. 排序后:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

时间复杂度:O(NlogN)
优点: 极快,数据移动少。
缺点:不稳定。


此条目是由 毅哥哥 发表在 记录 分类目录的 ,并贴了   标签

转载请注明作者和出处(小毅博客),并添加本页链接
原文链接: http://owexz.net/post/26

Java经典排序算法-快速排序》上有 0 条评论


必填项已用*标注