排序算法-快速排序

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

思路

• 宏观思路
  1.使用分治思想。选定一个基准元素，比基准元素小的元素放在基准元素左侧，比基准元素大的元素放在基准元素右侧。
  2.分别将基准元素左、右两次的数据按步骤1继续进行。
  

• 实现细节
  1.在数据序列中选出基准元素。
  2.定义两个指针（left，right），分别指向数组的左右两侧。如果right大于基准元素，right向左移动。如果left小于等于基准元素，left向右移动。如果left和right都不移动，则交换left、right所指向的元素。如果left与right指针重合，将该位置元素与基准元素交换。返回重合的位置作为分割的边界,分别对该位置左右两侧的元素进行排序。
  

  代码实现

  public class QuickSort{
     public static void quickSort(int[] arr,int startIndex,int endIndex){
         //递归结束条件
         if(startIndex >= endIndex){
             return;
         }
         //分区后返回的基准元素位置
         int pivotIndex = partition(arr,startIndex,endIndex);
         //根据基准元素分成两部分递归
         quickSort(arr,startIndex,pivotIndex - 1);
         quickSort(arr,pivotIndex + 1,endIndex);
  
     }    
     public static int partition(int[] arr,int startIndex,int endIndex){
         //获取基准元素
         int pivot = arr[startIndex];
         int left = startIndex;
         int right = endIndex;
  
         while(left != right){
             //控制right指针比较并左移
             while(left < right && arr[right] > pivot ){
                 right --;
             }
             //控制left指针比较并右移
             while(left < right && arr[left] <= pivot){
                 left ++;
             }
             //交换元素
             if (left < right) {
                 int temp = arr[left];
                 arr[left] = arr[right];
                 arr[right] = temp;
             }
         }
         //pivot 和 指针重合点交换
         int p = arr[left];
         arr[left] = arr[startIndex];
         arr[startIndex] = p;
         return left;
     }
     public static void main(String[] args) {
         int[] arr = new int[]{4,7,6,5,3,2,8,1};    
         quickSort(arr,0,arr.length - 1);
         for(int i = 0; i < arr.length; i++){
             System.out.println(arr[i]);
         }
     }
  }

• 非递归实现（用栈模拟递归）
  

  import java.util.Stack;
  import java.util.Map;
  import java.util.HashMap;
  public class QuickSort{
    public static void quickSort(int[] arr,int startIndex,int endIndex){
        //用一个集合栈代替递归
        Stack<Map<String,Integer>> quickSortStack = new Stack<>();
        //将整个数列的起止下标，以哈希的函数入栈
        Map<String,Integer> rootParam = new HashMap<>();
        rootParam.put("startIndex",startIndex);
        rootParam.put("endIndex",endIndex);
        quickSortStack.push(rootParam);
        //栈为空时循环结束
        while(!quickSortStack.isEmpty()){
            //栈顶元素出栈，得到起止下标
            Map<String,Integer> param = quickSortStack.pop();
            //得到基准元素的位置
            int pivotIndex = partition(arr,param.get("startIndex"),param.get("endIndex"));
            //根据基准元素将序列分成左右两部分，将这将部分数据分别入栈
            if(param.get("startIndex") < pivotIndex - 1){
                Map<String,Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex",param.get("startIndex"));
                leftParam.put("endIndex",pivotIndex - 1);
                quickSortStack.push(leftParam);
            }
            if(pivotIndex + 1 < param.get("endIndex")){
                Map<String,Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex",pivotIndex + 1);
                rightParam.put("endIndex",param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }    
    public static int partition(int[] arr,int startIndex,int endIndex){
        //获取基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
  
        while(left != right){
            //控制right指针比较并左移
            while(left < right && arr[right] > pivot ){
                right --;
            }
            //控制left指针比较并右移
            while(left < right && arr[left] <= pivot){
                left ++;
            }
            //交换元素
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //pivot 和 指针重合点交换
        int p = arr[left];
        arr[left] = arr[startIndex];
        arr[startIndex] = p;
        return left;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{4,7,6,5,3,2,8,1};    
        quickSort(arr,0,arr.length - 1);
        for(int i = 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }
  }