首页 > 代码库 > 常用算法Java实现之快速排序

常用算法Java实现之快速排序

  快速排序和冒泡排序相似,都是通过多次比较和交换来实现排序。
  具体流程如下:
  1、首先设定一个分界值,通过分界值将数组分成左右两部分,将大于等于分界值的数据交换集中到右侧数组,将小于分界值的数据交换集中到左侧数组;
  2、然后,左侧数组和右侧数组可以独立排序。对于左侧数组可以取一个分界值,将左侧数组分成左右两个部分,同样将左边放置小于分界值的数据,右侧放置大于等于分界值的数据。对右侧数组做类似处理。
  3、重复上述过程,其实就是递归。通过递归将左侧数组排好序后,再递归处理右侧数据。当左、右两部分数据都排好序后,整个数组的排序也就完成了。
    
  假如有初始数据:25  11  45  26  12  78。
  1、首先设定一个分界值,这里选择第一个元素---25。在变量left中保存数组的最小序号0,在变量right中保存数组的最大序号6,在变量base中保存分界值25。
  2、从数组右侧开始,逐个与分界值25比较,直到找到小于base的数据为止。这里,12 就比分界值25小。
  3、将右侧比分界值小的数据,保存到 A[left](A[0])元素中。
  4、从数组左侧开始,逐个与分界值25比较,直到找到大于等于base的数据为止。这里,数组最左侧的数据为12,比分界值小,将left自增1,再取A[left](A[1])的值为45,因45大于25,结束查找。
  5、将左侧比分界值大的数保存到A[right]元素中。
  6、将分界值保存到A[left]中。经过一轮比较和交换,base数据左侧的数都是比base值小的数,右侧都是比base值大的数。
  7、接下来,通过递归调用,将left左侧的数据进行同样的排序,再将left右侧的数据进行同样的排序。
 
  快速排序对冒泡排序进行了改进,因此具有更好的执行效率。平均时间复杂度是O(nlogn)。
 
  Java 代码实现如下:(https://github.com/xbk417/algorithm)
 1     public void sort(int[] arr) { 2         quickSort(arr, 0, arr.length - 1); 3     } 4      5     private static void quickSort(int[] arr, int left, int right){ 6         int t; 7         int ltemp = left; 8         int rtemp = right; 9         // 分界值10         int fIndex = arr[(left + right)/ 2];11         while(ltemp < rtemp) {12             // 从左侧开始查找比分界值大的数13             while(arr[ltemp] < fIndex) {14                 // 元素小于分界值,继续查找15                 ++ltemp;16             }17             // 从右侧开始查找比分界值小的数18             while(arr[rtemp] > fIndex) {19                 // 元素大于分界值,继续查找20                 --rtemp;    21             }22             // 如果查到的比分界值大的数的下标小于等于比分界值小的数的下标,则进行交换23             if(ltemp <= rtemp) {24                 t = arr[ltemp];25                 arr[ltemp] = arr[rtemp];26                 arr[rtemp] = t;27                 --rtemp;28                 ++ltemp;29             }30             if(ltemp == rtemp) {31                 ltemp++;32             }33             System.out.println( Arrays.toString(arr));34             if(left < rtemp) {35                 quickSort(arr, left, ltemp - 1);36             }37             if(ltemp < right) {38                 quickSort(arr, rtemp + 1, right);39             }40         }41     }

 

常用算法Java实现之快速排序