学排序看这一篇就够了

排序

• 排序概念
• 1.插入排序
• 2.选择排序
• 冒泡排序
• 快速排序
• 归并排序
• 总结对比

排序概念

• 稳定性：两个相等的数据，经过排序后，如果相对位置没有变化则为稳定排序，反之，为不稳定排序。
• 内部排序与外部排序：如果一次性可以将所有数据加载到内存中进行排序则为内部排序；反之，为外部排序

1.插入排序

1.1 直接插入排序

• 整个区间被分为：有序区间与无序区间；

• 原理：每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入。[默认要排序的数据第一个元素是有序的]

• 应用场景：如果搬移元素个数比较少，就比较适合插入排序，序列接近有序或者数据较少时

• 稳定性：稳定

• 时间复杂度：O(n^2)

  • 最优：O(n) -> 有序时
  • 最差：O(n^2) -> 逆序

• 空间复杂度：O(1)

• 代码实现：

  public static void insertSort(int[] array){
  	
      for(int i = 1; i < array.length;i++){
          //有序区间[0,i)
          //无序区间[i,array.length)
          int num = array[i]; //无序区间第一个数
          int end = i-1; //比较的元素位置
          
          while(end >= 0 && num < array[end]){ //当数组不越界同时当前数比相比较的数小的时候
              array[end+1] = array[end]; //移位
              end--;
          }
          
          //插入元素
          array[end+1] = num;
          
      }
  }
  

1.2 希尔排序

• 原理：采用分组的方式，将序列变成：接近有序，将数据变少；[采用直接插入排序对分组后的数据排序]

• 应用场景：元素比较凌乱，个数比较多

• 稳定性：不稳定

• 时间复杂度：O(n^2)

• 空间复杂度：O(n)

• 代码实现：

  public static void shellSort(int[] array){
  	int gap = array.length;
      while(gap > 1){
          gap = gap/3+1; //分组数
          for(int i = gap;i < array.length;i++){
              
              int num = array[i]; //分组后当前组中无序的第一个元素
              int end = i - gap;
              
              while(end >= 0 && num < array[end]){
                  array[end+gap] = array[end];
                  end -= gap;
              }
              
              array[end+gap] = num;
          }
      }
  }
  

2.选择排序

2.1 直接选择排序

• 原理：每次从无序区间选出最大(或最小)的一个元素，存放在无序区间的最后；直到全部元素排完[n个元素排n-1次]

• 稳定性：不稳定

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

• 代码实现：

  public static void selectSort(int[] array){
  	for(int i = 0;i < array.length-1;i++){
          
          //无序区间：[0,array.length-i）
          //有序区间：[arrar.length-i,array.length)
          int max = 0;
          for(int j = 1; j < array.length-i;j++){
              if(array[j] > array[max]){
                  max = j;
              }
          }
          
          int temp = array[max];
          array[max] = array[array.length-1-i];
          array[array.length-1-i] = temp;
      }
  }
  
  
  //双向选择排序
   public static void selectSortPlus(int[] array){
          int begin = 0;
          int end = array.length-1;
  
          while(begin < end){
              int min = begin;
              int max = begin;
  
              for (int i = begin+1; i <= end; i++) {
                  if(array[i] < array[min]){
                      min = i;
                  }
                  if(array[i] > array[max]){
                      max = i;
                  }
              }
  
              swap(array,min,begin);
  
              if(max == begin){
                  max = min;
              }
  
              swap(array,max,end);
              begin++;
              end--;
          }
  
      }
  

2.2 堆排序

• 原理：利用堆这种数据结构;首先建堆，利用堆删除的思想来进行排序(用堆顶元素与堆中最后一个元素进行交换，将堆中元素减少一个，再将堆顶元素向下调整)

• 稳定性：不稳定

• 时间复杂度：O(n*log(n))

• 空间复杂度：O(1)

  public satic void headSort(int[] array,int size){  //array排序数组，size数组长度
      creatHeap(array,size);
      
      for(int i = size-1;i >= 0;i--){
          swap(array,i,0); //将最大的节点与最后一个节点交换，以确保排序数组
         	shiftDown(array,size-1,0);//默认斩掉最后一个节点
      }
  }
  
  
  //构建堆
  private static void createHeap(int[] array,int size){
      int parent = (size-2)%2;
      
      for(int i = parent;i >= 0;i--){
          shiftDown(array,size,i);
      }
  }
  
  //向下调整
  public static void shiftDown(int[] array,int size,int index){
      int left = 2*index + 1;
      
      while(left < size){
          int max = left;
          int right = left + 1;
          if(right < size){
              if(array[right] > array[left]){
                  max = right;
              }
          }
          
          if(array[index] >= array[max]){
              break;
          }
          
          int temp = array[index];
          array[index] = array[max];
          array[max] = temp;
          
          index = max;
          left = 2*max+1;
      }
  }
  

3.冒泡排序

• 原理：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

• 稳定性：稳定

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

  public static void bubbleSort(int[] arr){
      for(int i = 0;i < arr.length-1;i++){
          boolean isSorted = true;
          for(int j = 0;i < arr.length-1-i;j++){
              if(array[j] > arr[j+1]){
                  swap(array,j,j+1); //交换
                  isSorted = false; 
              }
          }
          if(isSorted){ //如果没有交换则已排序完成
              break;
          }
      }
  }
  

4.快速排序

• 原理：默认升序

  1. 从区间中取出一个数据作为基准值，按照该基准值将区间分割左右两个部分
  2. 按照快排思想排序左半部分
  3. 按照快排思想排序右半部分

• 应用场景：数据量大比较随机(数据杂乱)

• 稳定性：不稳定

• 时间复杂度：O(n*logn)

• 空间复杂度：O(logn)

  //交换法
  //quickSort(array,0,array.length);[begin,end)
  public static void quickSort(int[] array,int begin,int end){
      if(end - begin > 1){
          int left = begin;
          int right = end-1;
          int baseNum = array[right];
          
          while(left < right){
              while(left < right && array[left] <= baseNum){
                  left++;
              }
              
              while(left < right && array[right] >= baseNum){
                  right--;
              }
              
              if(left < right){
                  swap(array,left,right);
              }
          }
          
          swap(array,end,left);
          
          quickSort(array,begin,left);
          quickSort(array,left+1,end);
      }
  }
  

  //挖坑法
  //quickSort(array,0,array.length-1);[begin,end]
   public static void quickSort(int[] array,int begin,int end){
          if(begin < end){
              int baseNum = array[begin]; //基数
              int left = begin;
              int right = end;
  
              while(left < right){
                  while(left < end && array[right] >= baseNum){
                      right--;
                  }
  
                  if(left < end){
                      array[left] = array[right];
                  }
  
                  while(left < end && array[left] =< baseNum){
                      left++;
                  }
  
                  if(left < end){
                      array[right] = array[left];
                  }
              }
  
              array[left] = baseNum;
              quickSort(array,begin,left-1);
              quickSort(array,left+1,end);
          }
      }
  

   //[ left , right):找到比基数小的给前面移动
      public static void quickSort(int[] array,int left,int right){
          if(right - left > 1){
              int cur = left;
              int prev = cur - 1;
              int key = array[right-1];
  
              while(cur < right){
                  if(key > array[cur] && ++prev != cur){  //++prev != cur是因为中间没有比基数大的了不用移动，自排序
                      swap(array,prev,cur);
                  }
                  ++cur;
              }
  
              if(++prev != right-1){
                  swap(array,prev,right-1);
              }
  
              quickSort(array,left,prev);
              quickSort(array,prev+1,right);
          }
      }
  

非递归实现：

​

    public static void quick(int[] array){
        Stack<Integer> stack = new Stack<Integer>();

        stack.push(array.length);
        stack.push(0);

        while(!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();

            if(right - left > 1){
                int div = quickSort(array, left, right);
                stack.push(right);
                stack.push(div+1);
                stack.push(div);
                stack.push(left);
            }
        }
    }

    public static int quickSort(int[] array,int left,int right){
            int cur = left;
            int prev = cur - 1;
            int key = array[right-1];

            while(cur < right){
                if(key > array[cur] && ++prev != cur){  //++prev != cur是因为中间没有比基数大的了不用移动，自排序
                    swap(array,prev,cur);
                }
                ++cur;
            }

            if(++prev != right-1){
                swap(array,prev,right-1);
            }

            return prev;
    }

5.归并排序

• 原理：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使

  子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

• 稳定性：稳定

• 时间复杂度：O(NlogN)

• 空间复杂度：O(n)

//合并两个有序数组
private static void merget(int[] array,int left,int mid,int right,int[] temp){
        int index1 = left;
        int index2 = mid+1;
        int index = 0;
        while(index1 <= mid && index2 <= right){
            if(array[index1] <= array[index2]){
                temp[index++] = array[index1++];
            }else{
                temp[index++] = array[index2++];
            }
        }

        while(index1 <= mid){
            temp[index++] = array[index1++];
        }

        while(index2 <= right){
            temp[index++] = array[index2++];
        }

//        index = 0;
//        while(left <= right){
//            array[left++]=temp[index++];
//        }
        System.arraycopy(temp,0,array,left,right-left+1);
    }

//递归实现归并排序[left,right]
 private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left < right){
            int mid = (left+right)/2;

            //向左递归
            mergeSort(arr,left,mid,temp);
            //向右递归
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

//非递归 实现归并排序
public static void mergetSort(int[] array){
        int gap = 1;
        int[] temp = new int[array.length];
        while (gap < array.length){
            for(int i= 0;i < array.length;i+=gap*2){
                int mid = i+gap;
                int right = mid+gap;

                if(mid >= array.length){
                    mid = array.length-1;
                }

                if(right >= array.length){
                    right = array.length-1;
                }

                merget(array,i,mid,right,temp);
            }
            gap*=2;
        }
    }

总结

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n)	O(n^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(n*logn)	O(n*logn)	O(n*logn)	O(1)	不稳定
快速排序	O(n*logn)	O(n*logn)	O(n^2)	O(logn)~O(n)	不稳定
归并排序	O(n*logn)	O(n*logn)	O(n*logn)	O(1)	稳定