常用排序算法

1. 冒泡排序-Bubble

• 记录当前需比较的个数

• 从一端开始比较，将最大(最小)的数据移至另一侧，比较个数减一

• 重复步骤直到所有数据都已完成移动

  public static int[] bubbleSwap(int[] nums){
      int length = nums.length;
      for (int i = length-1; i > 0; i--) {//记录当前还需比较的位置个数
          boolean hasChange = false;//如果未发生数据交换表明，这些数据不需要再进行交换了
          for (int j = 0; j < i; j++) {
              if (nums[j]>nums[j+1]) {
                  int min =nums[j];
                  nums[j]=nums[j+1];
                  nums[j+1]=min;
                  hasChange = true;
              }
          }
          if (!hasChange) {
              break;
          }
      }
      return nums;
  }
  

2. 选择排序-Choose

• 找到数组中最大（小）的元素，与第一个（或最后一个）进行交换

• 在剩下的元素中继续上述操作，直到结束

  public static int[] chooseSwap(int[] nums) {
      int length = nums.length;
      for (int i = 0; i < length - 1; i++) {
          int index =i;//指向这轮最小的位置；
          for (int j = i; j < length; j++) {
              if (nums[index]>nums[j]) {
                  index = j;
              }
          }
          //交换
          int temp = nums[index];
          nums[index] = nums[i];
          nums[i] = temp;
      }
      return nums;
  }
  

3. 插入排序-insert

• 从左（右）侧开始遍历，视当前位置前（后）为有序部分，对当前元素进行插入

• 找到位置对有序部分进行元素移动，直到遍历完成

• 插入算法可以优化为 二分查找插入，提高比较效率

  public static int[] insertSwap(int[] nums) {
      int length = nums.length;
      int currValue;
      for (int i = 0; i < length - 1; i++) {
          int preIndex = i;//已排序的索引位置
          currValue = nums[preIndex + 1];//对后一位向前遍历插入
          while (preIndex >= 0 && currValue < nums[preIndex]) {
              nums[preIndex + 1] = nums[preIndex];//较大的元素向后移动一位
              preIndex--;
          }
          //二分查找插入位置
          //int left = 0;
          //int right = i - 1;
          //int mid = 0;
          //while (left <= right) {
          //    mid = (left + right) / 2;
          //    if (nums[mid] < currValue) {
          //        left = mid + 1;
          //    } else {
          //        right = mid - 1;
          //    }
          //}
          nums[preIndex + 1] = currValue;//找到较小位置或小于0，在后面插入该值
      }
      return nums;
  }
  

4. 希尔排序- Shell

• 基于插入排序：可以理解为插入是最小量的排序，在插入中，有序部分下标间隔是1，在希尔当中这个间隔量是不断缩小最终为1的

• 目的是为了在数据量过长时，缩小移动次数

  public static int[] shellSwap(int[] nums) {
      int length = nums.length;
      int currValue;
      int gap = length / 2;
      while (gap > 0) {
          for (int i = gap; i < length; i++) {
              int preIndex = i-gap;//组内已排序的索引位置
              currValue = nums[i];//对后gap位向前遍历插入
              while (preIndex >= 0 && currValue < nums[preIndex]) {
                  nums[preIndex + gap] = nums[preIndex];//较大的元素向后移动gap位
                  preIndex-=gap;
              }
              nums[preIndex + gap] = currValue;//找到较小位置或小于0，在后面插入该值
          }
          gap /= 2;
      }
      return nums;
  }
  

5. 归并排序-merge

• 将数据进行对半分解，再细分到一定程度时，可使用其他算法进行排序，最后再对这些有序子数据集合进行合并（二路、多路-合并）

• 运用分治思想，先分解后合并

  public static int[] mergeSwap(int[] nums) {
      if (nums==null||nums.length<2) {
          return nums;
      }
      int length = nums.length;
      int mid = length / 2;
      int[] left = Arrays.copyOfRange(nums, 0, mid);
      int[] right = Arrays.copyOfRange(nums, mid, length);
      return merge(mergeSwap(left),mergeSwap(right));
  }
  
  public static int[] merge(int[] left, int[] right) {
      int lLength = left.length;
      int rLength = right.length;
      int[] results = new int[lLength + rLength];
      int length = results.length;
      for (int l = 0, r = 0, i = 0; i < length; i++) {
          if (l > lLength - 1) {
              results[i] = right[r++];
          } else if (r > rLength - 1) {
              results[i] = left[l++];
          } else {
              if (left[l] > right[r]) {
                  results[i] = right[r++];
              } else {
                  results[i] = left[l++];
              }
          }
      }
      return results;
  }
  

6. 快速排序-Quick

• 在数据中以某个元素为基准，找到它在所有数据中的正确位置，并分割为左右两个数据集合

  • 双指针法：左侧遍历，小于时跳过，大于时停止并交换位置；右侧遍历，大于时跳过，小于时停止并交换位置；跳出时更新位置数据
    若已左侧第一个为基准，则先从从右侧开始遍历交换该数据

• 左右两端重复上述操作，直到无法分割即所有数据均找到正确位置

  public static int[] quickSwap(int[] nums,int start,int end){
      if (start<end) {
          int mid = findPosition(nums, start, end);
          quickSwap(nums, start, mid - 1);
          quickSwap(nums, mid + 1, end);
      }
      return nums;
  }
  public static int findPosition(int[] args, int start, int end) {
      int pivot = args[start];//以左侧为基准值
      while (start < end) {//为双指针， 重合时跳出
          // 从右向左寻找，一直找到比参照值还小的数值，进行替换
          while (start < end && args[end] >= pivot) {
              end--;//找到比基准值小的数值的位置
          }
          if (start < end) {
              //因为基准值已被记录，所以直接更新即可，args[end]会在下一次更新
              args[start] = args[end];
          }
          // 从左向右寻找，一直找到比参照值还大的数组，进行替换
          while (start < end && args[start]  < pivot) {
              start++;
          }
          if (start < end) {
              args[end] = args[start];
          }
      }
      args[start] = pivot;//此时 双指针都指向了应该在的位置，更新该值即可
      return start;
  } 
  

7. 堆排序-Heap

• 构建大堆（是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点 ）

• 每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，依次类推，最终得到排序的序列。

• 适合将数据转换为有序的状态，但不需要完全有序

  public static int[] heapSwap(int[] nums) {
      //建立最大堆 从最后一个非叶子节点(len/2-1)开始向上构造最大堆
      int len = nums.length;
      for (int i = (len / 2 - 1); i >= 0; i--) {
          adjustHeap(nums, i, len);
      }
      //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
      while (len > 0) {
          int temp = nums[0];
          nums[0] = nums[len - 1];
          nums[len - 1] = temp;
          len--;
          adjustHeap(nums, 0, len);
      }
      return nums;
  }
  public static void adjustHeap(int[] nums, int i, int len) {
      int maxIndex = i;
      int left = 2 * i + 1;
      int right = 2 * (i + 1);
      //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
      if (left < len && nums[left] > nums[maxIndex])
          maxIndex = left;
      //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
      if (right < len && nums[right] > nums[maxIndex])
          maxIndex = right;
      //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
      if (maxIndex != i) {
          int temp = nums[maxIndex];
          nums[maxIndex] = nums[i];
          nums[i] = temp;
          adjustHeap(nums, maxIndex, len);
      }
  }
  

8. 计数排序-count

• 只针对一定范围内的整数进行排序，速度较快

• 遍历寻找元素中最大值、最小值及偏移量，用来确定计数数组的大小

• 遍历，将元素的值转换为计数数组下标

• 遍历，将技术数组不为0的数据的下标转换为原数组位置数据

  public static int[] countSwap(int[] nums) {
      if (nums == null || nums.length < 2) {
          return nums;
      }
      int min = nums[0];
      int max = nums[0];
  
      for (int num : nums) {
          if (min > num) {
              min = num;
          }
          if (max < num) {
              max = num;
          }
      }
      int bias = 0 - min;
      int[] counterArray = new int[max - min + 1];
      for (int i = 0; i < nums.length; i++) {
          //遍历整个原始数组，将原始数组中每个元素值转化为计数数组下标，并将计数数组下标对应的元素值大小进行累加/
          counterArray[nums[i] + bias]++;
      }
      int index = 0;//访问原始数组时的下标计数器
      int i = 0;//访问计数数组时的下标计数器
      while (index < nums.length) {
          //访问计数数组，将计数数组中的元素转换后，重新写回原始数组
          //只要计数数组中当前下标元素的值不为0，就将计数数组中的元素转换后，重新写回原始数组
          if (counterArray[i] != 0) {
              nums[index] = i - bias;
              counterArray[i]--;
              index++;
          } else {
              i++;
          }
      }
      return nums;
  }
  

9. 桶排序-bucket

• 输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）

• 数据找出最大最小值，按size计算出桶个数

• 数据根据自身值分配对应桶中（初步有序），用其他算法对桶内部排序（内部有序），最后数据统一取出

  public static List<Integer> bucketSwap(List<Integer> nums, int bucketSize) {
      if (nums == null || nums.size() < 2) {
          return nums;
      }
      int min = nums.get(0);
      int max = nums.get(0);
      for (int num : nums) {
          if (min > num) {
              min = num;
          }
          if (max < num) {
              max = num;
          }
      }
      int bucketCount = (max - min) / bucketSize + 1;//桶的数量
      List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);//构建桶
      List<Integer> resultArr = new ArrayList<>();
      for (int i = 0; i < bucketCount; i++) {
          bucketArr.add(new ArrayList<Integer>());
      }
      //将原始数组中的数据分配到桶中/
      for (int i = 0; i < nums.size(); i++) {
          bucketArr.get((nums.get(i) - min) / bucketSize).add(nums.get(i));
      }
      for (int i = 0; i < bucketCount; i++) {
          if (bucketSize == 1) {
              for (int j = 0; j < bucketArr.get(i).size(); j++){
                  resultArr.add(bucketArr.get(i).get(j));
              }
          } else {
              if (bucketCount == 1) {
                  bucketSize--;
              }
              //对桶中的数据进行排序
              List<Integer> temp = bucketSwap(bucketArr.get(i), bucketSize);
              for (int j = 0; j < temp.size(); j++) {
                  resultArr.add(temp.get(j));
              }
          }
      }
      return resultArr;
  

10. 基数排序-radix

• 基数排序不是基于比较的算法 。
  基数：对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能， 那10就是它的基 。二进制数字的基为2 。

• 从右往左（个位-->最大位）的顺序，依次遍历按位排序，对于同长度的数来说，当前轮完成遍历时对应顺序也就完成了排序（所以要以每一次遍历后的结果来作为下一次遍历的基础）

• 最大轮次为最大数的长度

  public static int[] radixSwap(int[] nums,int radix) {
      if (nums == null || nums.length < 2) {
          return nums;
      }
      int max = nums[0];//找出最大数
      for (int num : nums) {
          if (max < num) {
              max = num;
          }
      }
      int maxDigit = 0;//先算出最大数的位数
      while (max != 0) {
          max /= 10;
          maxDigit++;
      }
  
      int mod = radix, div = 1;
      List<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();//构建桶
      for (int i = 0; i < radix; i++) {
          bucketList.add(new ArrayList<Integer>());
      }
      for (int i = 0; i < maxDigit; i++, mod *= radix, div *= radix) {//按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮排序都基于上轮排序后的结果 /
          /*遍历原始数组，投入桶中*/
          for (int j = 0; j < nums.length; j++) {
              int num = (nums[j] % mod) / div;
              bucketList.get(num).add(nums[j]);
          }
          int index = 0;
          for (int j = 0; j < bucketList.size(); j++) {
              for (int k = 0; k < bucketList.get(j).size(); k++) {
                  nums[index++] = bucketList.get(j).get(k);
              }
              bucketList.get(j).clear();
          }
      }
      return nums;
  }
  

算法比较

image