内排序_算法

概述

根据排序元素所在位置的不同,排序分: 内排序和外排序。

​ 内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
​ 外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

分类

图1

比较：需要比较两个元素的大小(前后)才能进行的排序。

插入：遍历到的元素放入之前维护的已完成排序的序列中。

交换：每次只调换两个元素之间的位置。

选择：选择剩余元素中最大或最小的元素。

稳定性

​ 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

​ 意义：排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法。例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。

比较类排序

交换排序

冒泡排序

​ 冒泡排序对基本思想：通过无序区中相邻元素间关键字的比较和位置的交换，使关键字最小的元素如气泡一样逐渐上浮。

算法描述

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

public static void buttleSort(int[] nums) {
  for (int i = 0; i < nums.length - 1; i++) {
    for (int j = 0; j < nums.length - 1; j++) {
      if (nums[j] > nums[j + 1]) {//两元素比较交换,升序
        int tmp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = tmp;
      }
    }
  }
}

快速排序

​ 快排是由冒泡排序改进而来，基本思想：在待排序的n个元素中任取一个座位基准，把该元素放入合适位置，数据序列被分为两部分，所有比该元素小的在前一部分，所有比该元素大的在后一部分。这个过程为一趟快速排序，然后在前后两部分内分别重复上述步骤。直至子表的长度为1或者0。

算法描述：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

private static void quickSort(int[] nums, int left, int right) {
  if (left < right) {
    int partitionIndex = partition(nums, left, right);
    quickSort(nums, left, partitionIndex - 1);
    quickSort(nums, partitionIndex + 1, right);
  }
}
private static int partition(int[] nums, int left, int right) {
  int pivot = left;//基准值
  int index = pivot + 1;
  for (int i = index; i <= right; i++) {
    if (nums[i] > nums[pivot]) {//降序
      int tmp = nums[i];
      nums[i] = nums[index];
      nums[index] = tmp;
      index++;
    }
  }
  int tmp = nums[pivot];
  nums[pivot] = nums[index - 1];
  nums[index - 1] = tmp;
  return index - 1;
}

插入排序

插入排序

​ 插入排序的思路：待排序列分为有序区和无序区，然后将无序区中的元素插入到有序区中合适的位置。

算法描述：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

方括号内的为有序区域。

private static void insertionSort(int[] nums) {
  for (int i = 1; i < nums.length; i++) {
    int current = nums[i];
    int j = i - 1;
    for (; j >= 0; j--) {
      if (nums[j] < current) {//升序
        nums[j + 1] = current;
        break;
      } else {
        nums[j + 1] = nums[j];
      }
    }
    if (j == -1) {
      nums[j + 1] = current;
    }
  }
}

希尔排序

​ 希尔排序为一种分组插入排序。基本思想为：先去定一个小于n的整数d1，作为第一个增量，然后把全部元素分为d1个组，所有相互间距离为d1的倍数的元素放在同一个组，各组内进行插入排序。然后去第二个增量d2.重复上述步骤，直至di=1.

算法描述：

1. 选择一个增量序列gap1，gap2，…，gapk，其中gapi>gapj，gapk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量gapi，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

对于关键字{9,8,7,6,5,4,3,2,1,0}

d=5时，分组为：(9,4),(8,3),(7,2),(6,1),(5,0).组内插排的结果为(4,9),(3,8),(2,7),(1,6),(0,5)

d=2时，分组为：(4,2,0,8,6),(3,1,9,7,5).组内插排的结果为(0,2,4,6,8),(1,3,5,7,9)

d=1时，分组为：(0,2,4,6,8,1,3,5,7,9).组内插排的结果为(0,1,2,3,4,5,6,7,8,9)

private static void shellSort(int[] nums) {
  int gap = nums.length / 2;//增量初始值
  while (gap > 0) {
    for (int i = gap; i < nums.length; i++) {//对间隔gap位置对元素进行直接插入排序
      int tmp = nums[i];
      int j = i - gap;
      while (j >= 0 && tmp < nums[j]) {
        nums[j + gap] = nums[j];
        j = j - gap;
      }
      nums[j + gap] = tmp;
    }
    gap = gap / 2;//减小增量
  }
}

选择排序

简单选择排序

​ 基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述：

​ n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果：

1. 初始状态：无序区为R[1…n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

private static void selectionSort(int[] nums) {
  for (int i = 0; i < nums.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < nums.length; j++) {//寻找最值
      if (nums[minIndex] > nums[j]) {
        minIndex = j;
      }
    }
    int tmp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = tmp;
  }
}

堆排序

​ 堆：n个关键字序列K1,K2…Kn成为堆，当且仅当该序列满足如下：

1. Ki<=K2i&&Ki<=K(2i+1)

   或

2. Ki>=K2i&&Ki>=K(2i+1)

   满足条件1为小根堆，满足条件2为大根堆。

​ 堆排序是一种树形选择排序方法，在排序过程中，将nums[1…n]看作为一棵完全二叉树的顺序存储，利用完全二叉树双亲节点和孩子节点之间的内在关系，选择当前堆中的最大或最小元素。

算法描述：

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

private static void heapSort(int[] nums) {
  //为了计算方便，数组下标从1开始计算，而不是从0开始计算
  for (int i = (int) Math.floor(nums.length / 2); i >= 1; i--) {
    //这里传递的参数应该是最后一个元素的数组下标，而不是数组长度。
    sift(nums, i, nums.length - 1);//构建大根堆。从最后一个非叶子节点开始，比较该节点和子节点的大小。
  }
  for (int i = nums.length - 1; i >= 2; i--) {
    int tmp = nums[1];
    nums[1] = nums[i];
    nums[i] = tmp;
    sift(nums, 1, i - 1);
  }
}

private static void sift(int[] nums, int low, int high) {//构建大根堆
  int i = low;
  int j = 2 * i;//nums[j]是nums[i]的右孩子
  int tmp = nums[i];
  while (j <= high) {
    if (j < high && nums[j] < nums[j + 1]) {//如果左孩子大于右孩子，则将j指向左孩子。
      j++;//j指向两个孩子中较大的那个
    }
    if (tmp < nums[j]) {//较大的孩子节点大于父节点
      nums[i] = nums[j];//将nums[j]调整到父节点的位置
      i = j;
      j = 2 * i;
    } else {
      break;
    }
  }
  nums[i] = tmp;
}

归并排序

​ 二路归并的基本思想是：将R[0,…n]看出n个长度为1的有序序列，然后进行两两归并，然后得到n/2个长度为2的有序序列，在进行两两归并，然后得到n/4个长度为4的有序序列…直到得到一个长度有n的有序序列。

算法描述：

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

private static void mergeSort(int[] nums, int n) {
  for (int i = 1; i < n; i = i * 2) {//i为每次归并的长度
    megrePass(nums, i, n);
  }
}
private static void megrePass(int[] nums, int length, int n) {
  int i = 0;
  for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) {
    megre(nums, i, i + length - 1, i + 2 * length - 1);
  }
  if (i + length - 1 < n) {
    megre(nums, i, i + length - 1, n - 1);
  }
}
private static void megre(int[] nums, int low, int mid, int high) {
  int[] tmp = new int[high - low + 1];//存放中间结果
  int i = low;
  int j = mid + 1;
  int k = 0;
  while (i <= mid && j <= high) {
    if (nums[i] < nums[j]) {
      tmp[k] = nums[i];
      k++;
      i++;
    } else {
      tmp[k] = nums[j];
      k++;
      j++;
    }
  }
  while (i <= mid) {//前半段的剩余部分处理完
    tmp[k] = nums[i];
    k++;
    i++;
  }
  while (j <= high) {//后半段的剩余部分处理完
    tmp[k] = nums[j];
    k++;
    j++;
  }
  for (k = 0, i = low; i <= high; k++, i++) {//将归并的结果复制回nums中
    nums[i] = tmp[k];
  }
}

非比较排序

计数排序

​ 计数排序是一个非基于比较的排序算法，作为一种线性时间复杂度的排序，采用牺牲空间换取时间的做法来使其快于任何比较排序算法。计数排序要求输入的数据必须是有确定范围的整数。

算法描述：

1. 找出原数组中元素值最大的，记为max。
2. 创建一个新数组count，其长度是max加1，其元素默认值都为0。
3. 遍历原数组中的元素，以原数组中的元素作为新数组count的索引，以原数组中的元素出现次数作为新数组count的元素值。
4. 遍历新数组count，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到原数组中去，每处理一次，新数组count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

private static int[] countingSort(int[] nums, int length) {
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < nums.length; i++) {
    if (max < nums[i]) {
      max = nums[i];
    }
  }
  int[] count = new int[max + 1];
  for (int i = 0; i < nums.length; i++) {
    count[nums[i]]++;
  }
  int index = 0;
  for (int i = 0; i < count.length; ) {
    if (count[i] <= 0) {
      i++;
      continue;
    } else {
      count[i]--;
      nums[index] = i;
      index++;
    }
  }
  return nums;
}
}

桶排序

​ 桶排序是计数排序的升级版。利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。原理：将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

算法描述：

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

public static void basket(int nums[]) {
  int min = Integer.MAX_VALUE;
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] > max) {
      max = nums[i];//最大值
    }
    if (nums[i] < min) {
      min = nums[i];//最小值
    }
  }
  int bucketSize = 5;//设置5个桶
  int[][] buckets = new int[bucketSize][nums.length];
  int[] index = new int[bucketSize];

  int count = (int) Math.floor((max - min) / (bucketSize - 1));

  for (int i = 0; i < nums.length; i++) {//利用映射函数将数据分配到各个桶中
    buckets[(int) Math.floor((nums[i] - min) / count)][index[(int) Math.floor((nums[i] - min) / count)]++] = nums[i];
  }
  int number = 0;
  for (int i = 0; i < buckets.length; i++) {//每个桶里用选择排序

    int[] tmp = new int[index[i]];
    for (int j = 0; j < tmp.length; j++) {
      tmp[j] = buckets[i][j];
    }
    SelectionSort.selectionSort(tmp);
    for (int j = 0; j < tmp.length; j++) {
      nums[number++] = tmp[j];
    }
  }
}

基数排序

​ 基数排序有两种：最低为优先和最高位优先。最低位优先的过程：先按照最低位的值对元素进行排序，在此基础上，再依次低位进行排序，以此类推，有低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有元素进行排序，直至最高位。

算法描述：

1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。

private static void radixSort(int[] nums) {
  int max = Integer.MIN_VALUE;
  int bask[][] = new int[10][nums.length];
  int index[] = new int[10];
  for (int i = 0; i < nums.length; i++) {//最大位数
    max = max > (Integer.toString(nums[i]).length()) ? max : (Integer.toString(nums[i]).length());
  }

  for (int i = max - 1; i >= 0; i--) {//依次从个位、十位。。。排序并收集
    for (int j = 0; j < nums.length; j++) {
      String str = "";
      if (Integer.toString(nums[j]).length() < max) {
        for (int k = 0; k < max - Integer.toString(nums[j]).length(); k++)
          str += "0";
      }
      str += Integer.toString(nums[j]);
      bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = nums[j];
    }
    int pos = 0;
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < index[j]; k++) {
        nums[pos++] = bask[j][k];
      }
    }
    for (int x = 0; x < 10; x++) {
      index[x] = 0;
    }
  }
}