排序算法.md

排序算法

交换排序

冒泡排序

• 重点是冒泡排序优化。

• 设置一个boolean值，如果某次循环已经没有进行交换，则后面不需要再循环。

快速排序

• 基准值、left、right、index（基准值位置）

• 从左往右找比基准值大的，从右往左找比基准值小的

• 平均时间复杂度：nlogn，最坏时间复杂度是n2

• public void Kuai(int [] arr, int startindex, int endindex){
          if (startindex >= endindex){
              return;
          }
          int po = arr[startindex];
          // 获取中间基准值位置
          int poindex = getIndex(arr,startindex,endindex);
          Kuai(arr,startindex,poindex-1);
          Kuai(arr,poindex + 1, endindex);
      }
      public int getIndex(int [] arr, int startindex, int endindex){
          // 找基准元素和基准元素的位置
          int povit = arr[startindex];
          int index = startindex;
          int right = endindex;
          int left = startindex;
          while(right>=left){
              while(left <= right){
                  // 从右往左找比基准元素小的
                  if (arr[right] <= povit){
                      arr[left] = arr[right];
                      index = right;
                      left++;
                      break;
                  }
                  right--;
              }
              // 从左往右，找比基准元素大的
              while(left <= right){
                  if (arr[left] > povit){
                      arr[right] = arr[left];
                      index = left;
                      right--;
                      break;
                  }
                  left++;
              }
          }
          arr[index] = povit;
          return index;
      }

插入排序

直接插入排序

• 解题思路：

• • 第一个值为已经排好序的值。第二个值与第一个值比较，如果小于则让第二个值的位置放上第一个位置，再把第一个位置放上原本第二个位置。以此类推

  • import java.util.ArrayList;
    
    public class Charu {
        public ArrayList<Integer> Cha(int [] arr){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int insertValue;
            for (int i = 1; i < arr.length; i++){
               insertValue = arr[i];
               int j = i - 1;
               for (; j >= 0 && insertValue < arr[j]; j--){// 注意这里的判断条件，因为for循环先执行j--再执行中间的判断条件，则后面要用j+1
                       arr[j+1] = arr[j];
    
               }
             //  System.out.println(j);
                arr[j+1] = insertValue;
            }
            for (int i = 0; i < arr.length; i++){
                list.add(i,arr[i]);
            }
            return list;
        }
    }

• 时间复杂度为n^2，控件复杂度为1

希尔排序

• 先将元素分组，再对分好组的元素进行直接插入排序。

• import java.util.ArrayList;
  
  public class Xier {
      public ArrayList<Integer> Xi(int [] arr){
          ArrayList<Integer> list = new ArrayList<Integer>();
          int d = arr.length;
          while(d > 1){
              d = d/2;
              // 确立前面顺序
              for (int i = 0; i < d; i++){
                  // 确立好后面顺序，与前面一一对应
                  for (int j = i+d; j < arr.length; j = j + d){
                      int temp = arr[j];
                      int x = j - d;
                      for (; x>=0 && arr[x] > temp; x = x - d){
                          arr[x+d] = arr[x];
                      }
                      arr[x+d] = temp;
                  }
              }
          }
          for (int i = 0; i < arr.length; i++){
              list.add(i,arr[i]);
          }
          return list;
      }
  }

• 平均时间复杂度是n^2；

• 不稳定的排序！！！

选择排序

简单选择排序

• 思想：从未排序的数组中拿出最小值，然后第一个值和最小值进行交换，指针挪到第二个位置；从后面找出最小值和第二个位置交换，指针挪到第三个，以此类推。

• import java.util.ArrayList;
  
  public class Xuanze {
      public ArrayList<Integer> Xuan(int [] arr){
          ArrayList<Integer> list = new ArrayList<Integer>();
          int min = arr[0];
          int minindex = 0;
          int temp = 0;
          Boolean ifchange = false;
          for (int i = 0; i < arr.length; i++){
              min = arr[i];
              // 查找是否有比min小的值
              int j = i + 1;
             for (; j < arr.length; j++){
                if (arr[j] <= min){
                    minindex = j;
                    min = arr[j];
                    ifchange = true;
                }
             }
              // 如果有，则进行交换位置，没有不进行，minindex遗留上一次的
             if (ifchange){
                 temp = arr[minindex];
                 arr[minindex] = arr[i];
                 arr[i] = temp;
                 ifchange = false;
             }
  
          }
  
          for (int i = 0; i < arr.length; i++){
              list.add(i,arr[i]);
          }
          return list;
      }
  }

• 时间复杂度为n^2，空间复杂度为1

堆排序

• 思想：先构建二叉堆，因为二叉堆的根节点总是最小或者最大，所以可以通过删除根节点来进行排序。每次删除都要重新调整堆。
• 时间复杂度为nlogn，空间复杂度为1；
• 都是不稳定排序。

归并排序

• 思想：先将数组分组，分成每个只有两个，排序。然后两两组合，成左右数组，进行下面步骤：左边第一个与右边第一个比较，举例：左小的话就放入集合中，左指针右移，继续比较，若右小，放入集合中，右指针右移。以此类推。