排序算法-快速排序

快速排序

快速排序（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]);
      }
  }
}