八大经典排序算法

表格总览

插入排序

插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

直接插入排序

从左往右，每次都以i+1为右边界，然后i+1的元素需要插入已经排好序的[0,i]的数组里，从后面一直比较到前面，遍历从i到0，只要有元素大于i+1那个元素就交换，最后插入成功后[0,i+1]就是排好序的数组了。

public static void insertSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i+1; j > 0; j--) {
            // 前者 > 后者，交换;
            if(arr[j-1] > arr[j]) {
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(change(arr));
}

希尔排序

缩小增量排序，对直接插入排序的一种改进，分组插入方法，每次都以rightStart=k为右边界的开始遍历，然后以比较0+k与k+k的方式遍历数组，前者大于后者就替换，直到k=0。

public static void shellSort(int[] arr) {
    int temp;
    int k = arr.length/2;
    while (k != 0) {
        for (int rightStart = k; rightStart < arr.length; rightStart++) {
            int left = rightStart - k;
            int right = rightStart;
            // 每次都是左右俩边对比
            while (right < arr.length) {
                if(arr[left] > arr[right]) {
                    temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
                left += k;
                right += k;
            }
        }
        k /= 2;
    }
    System.out.println(change(arr));
}

选择排序

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

直接选择排序

从左往右遍历，基于左边界的值进行比较，找到最小的元素进行替换，保证左边界的值是最小的。

public static void selectSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i+1; j < arr.length; j++) {
            // 参照物 > 目标，交换
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(change(arr));
}

堆排序

将待排序序列构成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其于末尾元素进行交换，此时末尾就为最大值，然后将剩余n-1个元素重新构成一个堆，这样就会得到n个元素的次小值，如此反复执行就能得到一个有序序列。

public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组
        buildMaxHeap(arr, len);
        // 交换堆顶和当前末尾的节点，重置大顶堆
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
    }
    private static void buildMaxHeap(int[] arr, int len) {
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (int)Math.floor(len / 2) - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }
    private static void heapify(int[] arr, int i, int len) {
        // 先根据堆性质，找出它左右节点的索引
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 默认当前节点（父节点）是最大值。
        int largestIndex = i;
        if (left < len && arr[left] > arr[largestIndex]) {
            // 如果有左节点，并且左节点的值更大，更新最大值的索引
            largestIndex = left;
        }
        if (right < len && arr[right] > arr[largestIndex]) {
            // 如果有右节点，并且右节点的值更大，更新最大值的索引
            largestIndex = right;
        }
        if (largestIndex != i) {
            // 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
            swap(arr, i, largestIndex);
            // 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整。
            heapify(arr, largestIndex, len);
        }
    }
    private static void swap (int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

交换排序

对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。

冒泡排序

每次遍历进行i与i+1的值进行比较，把大的值都往数组后面丢，保证了数组末尾的元素为最大。

public static int[] bubbleSort(int[] arr) {
    int temp;
    for(int i=arr.length-1;i>0;i--) {
        for(int j=0;j<i;j++) {
            // 前者如果小于后者，就调换
            if (arr[j] > arr[j+1]) {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(change(arr));
    return arr;
}

快速排序

快排都会以左边界的元素为参照值，然后把比它小的往左边丢，大的就往右边丢。

// 快排1
public static void fastSort1(int[] arr) {
    test62(arr, 0, arr.length - 1);
    System.out.println(change(arr));
}

// 快排2
public static void fastSort2(int[] arr,int left, int right) {
   if(left >= right) {
       return;
   }
   // 参照值
   int referenceIndex = left;
   int reference = arr[left];

   // 结束点
   int endIndex = right;

   int temp;
   int tempIndex = left;
   while (left < right) {

       // 右边边 > reference, 右边++
       while (left < right && arr[right] >= reference) {
           right--;
       }

       // 左边 < reference, 左边++
       while (left < right && arr[left] <= reference) {
           left++;
       }


       // 左边 > reference , 右边 < reference,就交换
       if(arr[left] > reference && arr[right] < reference) {
           temp = arr[left];
           arr[left] = arr[right];
           arr[right] = temp;
       }
       // 找到了中间点
       if(left == right) {
           tempIndex = left;
       }
   }
   // 交换参照值到指定位置，实现左边 < tempIndex < 右边
   temp = arr[referenceIndex];
   arr[referenceIndex] = arr[tempIndex];
   arr[tempIndex] = temp;

   // 往左边跟右边继续
   fastSort2(arr, referenceIndex, tempIndex);
   fastSort2(arr, tempIndex+1, endIndex);

}

归并排序

把大数组拆分成小数组不断进行比较排序得到最终结果。比如{1,2,3,4} => {1,2},{3.4} => {1}, {2},{3},{4}。
每次比较都需要新建一个临时一样大小的数组用来转比较结果。

// 归并1
public static void mergeSort1(int[] arr) {
    mergeSort2(arr, 0, arr.length - 1);
    System.out.println(change(arr));
}
// 归并2
public static void mergeSort2(int[] arr, int left, int right) {
    if(left == right) {
        return;
    }
    int mid = (right + left) / 2;
    mergeSort2(arr, left, mid);
    mergeSort2(arr, mid + 1, right);
    mergeSort3(arr, left, mid, right);
}

// 归并3
public static void mergeSort3(int[] arr, int left, int mid, int right) {
    // 比较2个数组的元素大小，设置到left 到 right里
    int leftIndex = left;
    int rightIndex = mid + 1;
    // 插入的临时排好序的数组;
    int[] tempArr = new int[right - left + 1];
    int tempIndex = 0;
    // 左边的界限为 left ---- mid，右边为 mid + 1  ----  right
    while(leftIndex <= mid && rightIndex <= right) {
        // 谁小，就设置谁
        if(arr[leftIndex] < arr[rightIndex]) {
            tempArr[tempIndex++] = arr[leftIndex++];
        } else {
            tempArr[tempIndex++] = arr[rightIndex++];
        }
    }

    // 遍历完，肯定只有一边的数组剩余，没加到临时数组里，加上
    while (leftIndex <= mid) {
        tempArr[tempIndex++] = arr[leftIndex++];
    }
    while (rightIndex <= right) {
        tempArr[tempIndex++] = arr[rightIndex++];
    }
    // 最后遍历设置到原数组里
    tempIndex = 0;
    for (int i = left;i<=right;i++) {
        arr[i] = tempArr[tempIndex++];
    }
}

基数排序

将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。