排序算法

对于排序过程中待排序的记录是否全部放置在内存中，排序分为内排序和外排序。

内排序：是指在整个排序过程中，待排序的所有记录都放在内存中，主要有插入排序、交换排序、选择排序和归并排序
外排序：是指待排序记录没有同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行

按照策略分类主要的排序算法有：插入排序、选择排序、交换排序、归并排序、分配排序

插入排序

插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，直到所有排序记录全部插入成功。

与选择排序一样的是，当前索引左边的所有元素都是有序的，但是最终位置还不确定，后续可能还会移动，当索引达到数组最右端时，数组排序完成

直接插入排序

首先对数组的前两个数据进行从小到大的排序
接着对第三个数据与排好序的两个数据进行比较，将第三个数据插入到合适的位置
然后将第4个数据插入到排好序的前三个数据中
重复上述操作

假设排序数据存放在数组A[1…n]中，则A[1]则可以看做是一个有序序列，让i从2开始，依次将A[i]插入到有序序列A[1…i-1]中，A[n]插入完毕结束

过程举例

【】中的数据为有序的

待排序的数据：	【 23】 56 2 9 17
i =2	【 23 56】 2 9 17
i=3	【 2 23 56】 9 17
i=4	【 2 9 23 56】17
i=5	【 2 9 17 23 56】

代码实现

int[] arrays = {67,67,14,52,29,9,90,54,87,71};

int i,j;
for(i = 1;i<arrays.length;i++){
    // 当前值比前一个值小  需要移位
    if(arrays[i] < arrays[i-1]){
        int temp = arrays[i]; // 暂存
        // 依次与前面的元素进行比较
        for(j = i-1;j >=0 && arrays[j] > temp;j--){
            arrays[j+1] = arrays[j];
        }
        // 找到所在位置
        arrays[j+1] = temp;
    }
}

第1次排序
[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]
第2次排序
[14, 67, 67, 52, 29, 9, 90, 54, 87, 71]
第3次排序
[14, 52, 67, 67, 29, 9, 90, 54, 87, 71]
第4次排序
[14, 29, 52, 67, 67, 9, 90, 54, 87, 71]
第5次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第6次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第7次排序
[9, 14, 29, 52, 54, 67, 67, 90, 87, 71]
第8次排序
[9, 14, 29, 52, 54, 67, 67, 87, 90, 71]
第9次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

平均时间复杂度O(n^2^)，最坏情况下为O(n^2^)，最好情况下是O(n)

插入排序对于部分有序的数组十分高效

希尔排序

希尔排序也是使用插入排序的思想，基于插入排序的快速的排序算法，由于大规模乱序数组插入排序很慢，只会交换相邻元素，一点一点地从数组的一端移动到另一端，希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序

将有n个元素的数组分为n/2个数字序列，第一个数据和第n/2+1个数据为一对…
一次循环使每一个序列对排好顺序
然后再变成n/4个序列，再次排序

任取一个小于n的正数S1作为增量，将所有的元素分为S1个组，先在各组进行直接插入排序，然后取第二个增量重复上述的分组和排序，直到所取的增量等于1，即所有记录放在同一个分组中为止

由于是每个组进行直接插入排序，所以是在直接插入排序上进行步长的设置

代码实现

步长的设置需要考量，慢慢尝试

int[] arrays = {67,67,14,52,29,9,90,54,87,71};

int i,j;
int gap = arrays.length /2;

while (gap >= 1){
    for(i = gap;i<arrays.length;i++){
        // 当前值比前一个值小  需要移位
        if(arrays[i] < arrays[i-1]){
            int temp = arrays[i]; // 暂存
            // 依次与前面的元素进行比较  将数据插入到 a[i-gap]、a[i-2*gap]、a[i-3*gap]...中
            for(j = i-gap;j >=0 && arrays[j] > temp;j=j-gap){
                arrays[j+gap] = arrays[j];
            }
            // 找到所在位置
            arrays[j+gap] = temp;
        }
    }
    gap = gap / 2;
    
}

=======================第1次
[9, 67, 14, 52, 29, 67, 90, 54, 87, 71]
=======================第2次
[9, 67, 14, 52, 29, 54, 90, 67, 87, 71]
=======================第3次
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

时间复杂度为O(nlog2^n^)，最坏情况下为O(n^2^)

希尔排序比插入排序快很多，并且数组越大，优势越大

交换排序

交换排序的基本思想是：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到没有反序为止

冒泡排序

冒泡排序是一种交换排序，基本思想是：两两比较相邻数据，如果反序则交换，直到没有反序为止

对数组中各数据，依次比较相邻的两个元素大小
如果前面的数据大于后面的数据，就交换这两个数据，每一轮都能把最大的数据排好
进行多轮就可以把数据按照从小到大的顺序排好

最多进行n-1趟排序，每趟排序自底向上扫描，一旦发现相邻的元素不符合规则，则交换，第一趟排序后，最小值在A[1]，第二次排序后，最小值在A[2]，依次类推，第n-1趟排序之后，所有元素按照顺序排列

代码实现

int[] arr = {67,67,14,52,29,9,90,54,87,71};
int count = 0;
for(int i = 0;i < arr.length - 1;i++){
  for(int j = 1; j < arr.length - i;j++){ // 为什么使用arr.length - i，因为每次排序，最大的都已经到了尾部，可以减少排序次数
    if(arr[j-1] > arr[j]){
      int temp = arr[j];
      arr[j] = arr[j-1];
      arr[j-1] = temp;
    }
  }
}


第1次排序后
67    14    52    29    9    67    54    87    71    90    
第2次排序后
14    52    29    9    67    54    67    71    87    90    
第3次排序后
14    29    9    52    54    67    67    71    87    90    
第4次排序后
14    9    29    52    54    67    67    71    87    90    
第5次排序后
9    14    29    52    54    67    67    71    87    90    
第6次排序后
9    14    29    52    54    67    67    71    87    90    
第7次排序后
9    14    29    52    54    67    67    71    87    90    
第8次排序后
9    14    29    52    54    67    67    71    87    90    
第9次排序后
9    14    29    52    54    67    67    71    87    90

平均时间复杂度为O(n^2^)，最坏情况下为O(n^2^)，最好情况下为O(n)，使用上述改良方式为O(n^2^/2)，稳定

快速排序

快排是冒泡排序的升阶版，从两端向中间进行排序，将一个数组分为两个子数组，将两部分独立地排序

采用的是分治的思想

首先设定一个分界值，通过分界值将数组分为左右两部分
将大于分界值的数据集中到数组右边，小于分界值的数据集中到数组左边，此时左边部分中各元素小于等于分界值，而右边部分中各元素大于等于分界值
然后左边和右边数据可以独立排序，分别取一个分界值来进行排序
重复上述过程

从集合中任取一个元素作为比较的基准X，将数据划分为左右两部分，A[1…i-1] <=X<=A[i+1…n]，然后在分别对它们进行划分，直到全部有序为止

代码实例

public class QuickSort {
    private static int count = 0;
    static int[] data = {67,67,14,52,29,9,90,54,87,71};
    public static void main(String[] args) {

        quickSort(0,data.length-1);
        System.out.println(Arrays.toString(data));
        System.out.println(count);
    }

    public static void quickSort(int begin,int end){
        if(begin == end || begin == (end - 1)){
            return;
        }
        // 取第一个数作为基准
        int p = data[begin];
        int low = begin+1;
        int hign = end;
        while (low < hign){
            count++;
            if(data[low] > p){
                if(data[hign] < p){
                    int temp = data[low];
                    data[low] = data[hign];
                    data[hign] = temp;
                }
                hign--;
            } else {
                low++;
            }
        }
        // low和hign位置碰撞时，可能数据还没有和基数比较
        if(data[low] > p){
            data[begin] = data[low-1];
            data[low-1] = p;
        } else {
            data[begin] = data[low];
            data[low] = p;
        }



        System.out.println(Arrays.toString(data));
        if(low-1 > begin){
            System.out.println("=====低位排序======");
            quickSort(begin,low-1);
        }
        if(end > hign+1){
            System.out.println("=====高位排序======");
            quickSort(hign+1,end);
        }

    }
}

=====低位排序======
[29, 9, 14, 52, 54, 67, 67, 90, 87, 71]
=====低位排序======
[14, 9, 29, 52, 54, 67, 67, 90, 87, 71]
=====低位排序======
[9, 14, 29, 52, 54, 67, 67, 90, 87, 71]
=====低位排序======
=====高位排序======
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]
=====低位排序======
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

平均时间复杂度为O(nlogn)，最坏情况下为O(n^2^)，最好情况下为O(nlogn)，不稳定

选择排序

选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素只有一个

直接选择排序

从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换
接着从剩下的n-1个数据中选择次小的1个元素，将其与第2个位置的数据交换
不断重复上述步骤，完成排序

过程举例

待排序数据
[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]
第1次排序
[9, 67, 14, 52, 29, 67, 90, 54, 87, 71]
第2次排序
[9, 14, 67, 52, 29, 67, 90, 54, 87, 71]
第3次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第4次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第5次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第6次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第7次排序
[9, 14, 29, 52, 54, 67, 67, 90, 87, 71]
第8次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]
第9次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

代码实现

for(int i = 0;i<data.length-1;i++){
  // 记录最小值得索引位置
  int min = i;
  for(int j = i+1;j<data.length;j++){

    if(data[min] > data[j]){
      min = j;
    }
  }
  // 找到最小位置后，进行交换
  if(min != i){
    int temp = data[i];
    data[i] = data[min];
    data[min] = temp;
  }
}

第1次排序
[9, 67, 14, 52, 29, 67, 90, 54, 87, 71]
第2次排序
[9, 14, 67, 52, 29, 67, 90, 54, 87, 71]
第3次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第4次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第5次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第6次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第7次排序
[9, 14, 29, 52, 54, 67, 67, 90, 87, 71]
第8次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]
第9次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

时间复杂度为O(n^2^)，最坏情况下为O(n^2^)，最好情况下为O(n^2^)，不稳定

堆排序

堆排序是一种树形选择排序，分为大顶堆和小顶堆

大顶堆：每个节点的值都大于等于其孩子节点的值
小顶堆：每个节点的值都小于等于其孩子的值

小顶堆

根节点的元素最小是小顶堆(小于左右子节点的值)

graph TD
0((0)) --- 1((1)) --- 3((3))
1((1)) --- 4((4))
0((0)) --- 2((2))

大顶堆

根节点的元素最大是大顶堆(大于左右子节点的值)

graph TD
0((4)) --- 1((3)) --- 3((1))
1((3)) --- 4((0))
0((4)) --- 2((2))

以小顶堆为例，由于每个节点的值都小于等于其子节点的值，而且其是一个完全二叉树，也就意味着父节点和其左右子节点的索引关系为2n+1和2n+2

值得关系为arr[n] <= arr[2n+1] arr[n]<=arr[2n+2]

public static void main(String[] args) {
    // 先找到最后一个元素的父节点索引
    int index = data.length/2-1;
    int length = data.length;
    for(int i = index;i>=0;i--){
        adjust(data,i,length);
    }
    // 将根节点与尾结点交换 得到新的无序数组 再次构建堆
    // 依次将根节点与无序数组中的最后一个元素替换 重复操作
      // 一直将堆顶元素放到堆的最后
    for (int i = length-1; i >0; i--) {
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        adjust(data, 0, i);
    }

    System.out.println(Arrays.toString(data));
    System.out.println(count);
}

public static void adjust(int[] data,int index,int length){
    int childLeftIndex = 2*index+1;
    int childRightIndex = 2*index+2;
    int lowIndex = index;
    count++;
    // 左孩子节点大于最小索引的值
    if(childLeftIndex < length && data[childLeftIndex] > data[lowIndex]){
        lowIndex = childLeftIndex;
    }
    // 右孩子节点大于最小索引的值
    if(childRightIndex < length && data[childRightIndex] > data[lowIndex]){
        lowIndex = childRightIndex;
    }

    // 与两个子节点都比较完在进行交换，否则会导致两个子节点的值被交换
    if(lowIndex != index){
        int temp = data[lowIndex];
        data[lowIndex] = data[index];
        data[index] = temp;

        // 数据交换之后可能会导致该值与其左右孩子节点的值大小不符合小顶堆，需要再次比较与其子树节点的大小关系
        adjust(data,lowIndex,length);
    }

}

时间复杂度为O(nlogn)，最坏情况下为O(nlogn)，最好情况下为O(nlogn)，不稳定

归并排序

归并排序是将待排序的数组分成几个长度几乎相等的子数组，然后使用插入排序对两个子数组中的每一个进行排序，再把两个排好序的子数组归并为一个，以此类推，若干个已排序的数组合并成一个有序的数组

static int[] data = {67,67,14,52,29,9,90,54,87,71};
static int[] temp = new int[data.length];
public static void main(String[] args) {
    sort(data,0,data.length-1);
    System.out.println(Arrays.toString(data));
}

// 排序
public static void sort(int[] arr,int start,int end){
    int middle = (start + end) / 2;
    if(start < end){
        // 分别排序
        sort(arr,start,middle);
        sort(arr,middle+1,end);
        merge(arr,start,middle,end);
    }
}


// 归并
public static void merge(int[] arr,int start,int middle,int end){
    int i = start;
    int j = middle+1;
    int k = 0;
    while (i <= middle && j <= end){
        if(arr[i] < arr[j]){
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 此时至少有一个序列是已经全部比较完的
    // 将没有比较完的一部分数据放到temp数组中
    if(i <= middle){
        System.arraycopy(arr,i,temp,k,middle-i+1);
    } else if(j<= end){
        System.arraycopy(arr,j,temp,k,end - j+1);
    }
    System.arraycopy(temp,0,arr,start,end - start+1);
}

平均时间复杂度为O(nlogn)，最坏情况下为为O(nlogn)，最好情况下为为O(nlogn)，稳定

各种排序对比

选择排序和冒泡排序

选择排序是从第一个数开始，与后面的数进行比较，找到最小的数，放在第一个位置。每轮只交换一次，交换的次数少
冒泡排序是从左往右，两两相互比较，然后交换位置。交换的次数多。