[数据结构与算法]常见排序算法及其实现——知识总结

• 排序：

  • 内部排序：数据记录在内存中进行排序
  • 外部排序：排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存

  

• 冒泡排序：

  1. 冒泡排序，是通过每一次遍历获取最大/最小值
  2. 将最大值/最小值放在尾部/头部
  3. 然后除开最大值/最小值，剩下的数据在进行遍历获取最大/最小值

  public static void main(String[] args) {
  		
      int arr[] = {8, 5, 3, 2, 4};
      //冒泡
      for (int i = 0; i < arr.length - 1; i++) {
        //外层循环，遍历次数
          for (int j = 0; j < arr.length - i - 1; j++) {
              //内层循环，升序（如果前一个值比后一个值大，则交换）
              //内层循环一次，获取一个最大值
              if (arr[j] > arr[j + 1]) {
                  int temp = arr[j + 1];
                  arr[j + 1] = arr[j];
                  arr[j] = temp;
              }
          }
      }
  }
  

  

• 选择排序：

  1. 将第一个值看成最小值
  2. 然后和后续的比较找出最小值和下标
  3. 交换本次遍历的起始值和最小值
  4. 说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值

  public static void main(String[] args) {
  
      int arr[] = {6, 5, 3, 2, 4};
  
      //选择
      for (int i = 0; i < arr.length; i++) {
          //默认第一个是最小的。
          int min = arr[i];
          //记录最小的下标
          int index = i;
          //通过与后面的数据进行比较得出，最小值和下标
          for (int j = i + 1; j < arr.length; j++) {
              if (min > arr[j]) {
                  min = arr[j];
                  index = j;
              }
          }
          //然后将最小值与本次循环的，开始值交换
          int temp = arr[i];
          arr[i] = min;
          arr[index] = temp;
          //说明：将i前面的数据看成一个排好的队列，i后面的看成一个无序队列。每次只需要找无需的最小值，做替换
      }
  }
  

  

• 插入排序：

  1. 默认从第二个数据开始比较
  2. 如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（狡猾）。否则，退出循环
  3. 说明：默认将第一数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出

  public static void main(String[] args) {
  
      int arr[] = {7, 5, 3, 2, 4};
  
      //插入排序
      for (int i = 1; i < arr.length; i++) {
          //外层循环，从第二个开始比较
          for (int j = i; j > 0; j--) {
              //内存循环，与前面排好序的数据比较，如果后面的数据小于前面的则交换
              if (arr[j] < arr[j - 1]) {
                  int temp = arr[j - 1];
                  arr[j - 1] = arr[j];
                  arr[j] = temp;
              } else {
                  //如果不小于，说明插入完毕，退出内层循环
                  break;
              }
          }
      }
  }
  

  

• 快速排序：

  1. 确认列表第一个数据为中间值，第一个值看成空缺（低指针空缺）
  2. 然后在剩下的队列中，看成有左右两个指针（高低）
  3. 开始高指针向左移动，如果遇到小于中间值的数据，则将这个数据赋值到低指针空缺，并且将高指针的数据看成空缺值（高指针空缺）。然后先向右移动一下低指针，并且切换低指针移动
  4. 当低指针移动到大于中间值的时候，赋值到高指针空缺的地方。然后先高指针向左移动，并且切换高指针移动。重复c、d操作
  5. 直到高指针和低指针相等时退出，并且将中间值赋值给对应指针位置。
  6. 然后将中间值的左右两边看成行的列表，进行快速排序操作

  public void quickSort(int [] arr,int L,int R){
      int i = L;
      int j = R;
      int mid = arr[(L+R)/2];
      while(i<=j){
  
          while(arr[i] > mid){
              i++;
          }
  
          while(arr[j] < mid){
              j--;
          }
  
          if(i<=j){
              swap(arr,i,j); //交换arr中下标为i、j的值
              i++;
              j--;
          }
      }
  
      if(L<j){
          quickSort(arr,L,j);
  	  }
  
      if(i<R){
          quickSort(arr,i,R);
  		}
  }
  
  public void swap(int[] arr,int i,int j){
      int temp;
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  
  public static void main(String[] args) {
      quickSort(arr,0,arr.length-1);    
  }