首先先上一个是十大排序算法对比图

image.png

1、冒泡排序（Bubble Sort）

算法流程:1、从头开始比较相邻的两个元素,如果第一个比第二个大,就交换他们的位置,执行完一轮后,就把最大的元素排到了最后一位
2、忽略最后一位，重新执行1，直到全部元素有序。
代码：

 protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin-1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }

优化1,如果全部有序就提前结束循环
优化2,如果部分有序,后面那部分有序的前一个索引,减少交换遍历次数

2、选择排序（Selection Sort）

算法流程:
1、从序列中找出最大的那个元素，然后与最末尾的元素进行交换，执行完一轮后，最末尾的那个元素就是最大的元素
2、忽略1中找到的最大元素，重复执行1

private static void selectionSort(Integer[] array) {
        for (int end = array.length - 1; end > 0; end--) {

            // 默认0号元素为最大值
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                // 为了保证排序的稳定性,要写>=
                if (array[begin] >= array[maxIndex]) {
                    maxIndex = begin;
                }
            }
            // 和最末尾的元素进行交换
            int temp = array[maxIndex];
            array[maxIndex] = array[end];
            array[end] = temp;
        }
        System.out.println(Arrays.toString(array));
    }

3、堆排序（Heap Sort）

堆排序可以认为是对选择排序的一种优化
算法流程:
1、对序列进行原地建堆（heapify）
2、重复执行以下操作,知道堆的元素数量为1
  （1）交换堆顶元素与尾元素
  （2）堆的元素数量减1
  （3）对0位置进行一次siftDown操作

image.png

image.png

image.png

image.png

image.png

image.png

public class HeapSort extends Sort{

    private int heapSize;
    @Override
    protected void sort() {
        // 原地建堆
        // 原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while(heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0,--heapSize);

            // 对0位置进行siftDown,(恢复堆的性质)
            siftDown(0);

        }
        //System.out.println(Arrays.toString(array));
    }

    private void siftDown(int index) {
        Integer element = array[index];

        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            Integer child = array[childIndex];

            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize &&
                    cmpElement(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }

            // 大于等于子节点
            if (cmpElement(element, child) >= 0) break;

            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}

4、插入排序(Inserttion Sort)

插入排序非常类似于扑克牌的排序

image.png

算法流程:
1、执行过程中会将序列分成两部分，前面的部分是排好序的，后面的部分是待排序的
2、从头到尾扫描每一个元素，每当扫到一个元素，就把他插入到合适的位置，使得前面的部分依然是排好序的

 protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int  cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur-1);
                cur--;
            }
        }
        //System.out.println(Arrays.toString(array));
    }

插入排序优化1,将交换变为挪动
1、先将待插入的元素备份
2、头部有序数据中比待插入元素大，都朝尾部方向挪动一个位置
3、将待插入元素放到最终合适的位置

image.png

  // 优化
    protected void sort1() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            Integer v = array[cur];

            while(cur > 0 && cmp(cur, cur - 1) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = v;
        }
    }

插入排序优化2
先来说一下二分搜索(Binary Search)

image.png

  二分搜索思路:
1、假设在[begin,end}的范围内搜索一个元素v,先找到位置中点的元素mid=array[(begin+end)>>1;]
2、如果v大于mid,则排除前半部分,begin=midIndex+1,重复执行1
3、如果v小于mid,则排除半部分,end = midIndx,重复执行1
4、如果v等于mid,直接返回mid

image.png

image.png

image.png

public  int indexOf(Integer[] array, int v) {
        if (array == null || array.length == 0) {
            return  -1;
        }
        int begin = 0;
        int end = array.length;

        while(begin < end) {
            int mid = (begin + end) >> 1;
            if (array[mid] < v) {
                begin = mid + 1;
            } else if (array[mid] > v) {
                end = mid;
            } else {
                return mid;
            }
        }
        return -1;

    }

插入查找优化代码

// 优化
    protected void sort2() {
        for (int begin = 1; begin < array.length; begin++) {
            Integer element = array[begin];
            int insertIndex = search(begin);
            for (int i = begin ; i > insertIndex ; i--) {
                array[i] = array[i -1];
            }
            array[insertIndex] = element;
        }
    }
    private  int search(int index) {
        int v = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (v >= array[mid]) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        return begin;
    }

5、归并排序

算法流程：
1、不断地将当前的序列平均分割成2个子序列
  直到不能再分割（序列中只剩一个元素）
2、不断将2个子序列合并成一个有序序列
  直到最终只剩下1个有序序列
图示

image.png

分割代码:

protected void sort() {
        leftArray =  new Integer[array.length >> 1];
        sort(0, array.length);
        System.out.println(Arrays.toString(array));
    }
    
    // T(n) = T(n/2) + T(n/2) + O(n)
    
    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }

归并merge细节

image.png

image.png

image.png

image.png

image.png

代码:

package dierjisuanfa.sort;


import java.util.Arrays;

public class MergeSort extends Sort {
    private Integer[] leftArray;

    @Override
    protected void sort() {
        leftArray =  new Integer[array.length >> 1];
        sort(0, array.length);
        System.out.println(Arrays.toString(array));
    }
    
    // T(n) = T(n/2) + T(n/2) + O(n)
    
    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }
    
    /**
     * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;
        
        // 备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }
        
        // 如果左边还没有结束
        while (li < le) {

                if (ri < re && array[ri]<leftArray[li]) {
                    array[ai++] = array[ri++];
                } else {
                    array[ai++] = leftArray[li++];
                }
            }

    }
}

6、快速排序

算法流程：
1、从序列中选择一个轴点元素（pivot）
  假设每次选择0位置为轴点元素
2、利用pivot将序列分割成两个子序列
  将小于pivot的元素放在pivot左侧
  将大于pivot的元素放在pivot右侧
  等于pivot的元素放在哪边都可以
3、对子序列进行1,2操作
  直到不能再分割（子序列中只剩下1个元素）
图示

image.png

image.png

image.png

代码：

package dierjisuanfa.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 1.从序列中选择一个轴点元素
 *      假设每次选择0位置的元素为轴点元素
 *
 * 2.利用pivot将序列分割为2个子序列
 *      将小于pivot的元素放在pivot前面(左侧)
 *      将大于pivot的元素放在pivot后面(右侧)
 * 3.对子序列进行1,2操作
 *      直到不能再分割(子序列只剩一个元素)
 *
 * 快速排序的本质
 * 逐渐将每一个元素都转换成轴点元素
 */
public class QuickSort extends Sort{
    @Override
    protected void sort() {
        sort(0, array.length);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 对[begin, end)范围的元素进行快速排序
     * @param beign
     * @param end
     */
    private void sort(int beign, int end){
        if(end - beign < 2) {
            return;
        }

        // 确定轴点位置
        int mid = pivotIndex(beign, end);
        // 对子序列也进行快速排序
        sort(beign, mid);
        sort(mid + 1, end);
    }

    /**
     * 确定[begin,end)范围的轴点元素
     * @param beign
     * @param end
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int beign, int end) {
        // 随机选择一个元素跟begin位置进行交换
        swap(beign,beign + (int)(Math.random()*(end-beign)));
        // 备份begin位置的元素
        Integer pivot = array[beign];
        end--;

        while(beign < end) {
            while(beign < end) {
                // 从右往左扫描
                if(cmpElement(pivot,array[end]) < 0) {// 右边元素 > 轴点元素
                    end--;
                } else {
                    array[beign] = array[end];
                    beign++;
                    break;
                }
            }
            while(beign < end) {
                // 从左往右扫描
                if (cmpElement(pivot, array[beign]) > 0) {
                    beign++;
                } else {
                    array[end] = array[beign];
                    end--;
                    break;
                }
            }


        }
        // 将轴点元素放入最终位置
        array[beign] = pivot;
        // 返回轴点元素的位置
        return beign;
    }
}

7、希尔排序

希尔排序把序列看作是一个矩阵，分为m列，逐列进行排序
m从某个整数逐渐减为1
当m为1是，整个序列将完全有序

希尔排序也被称为递减增量排序

矩阵的列数取决于步长序列
比如，如果步长序列为{1,5,19,41,109},就代表依次分为109列,41列,19列,5列,1列进行排序
不同的步长序列,执行效率也不同

image.png

image.png

image.png

image.png

image.png

代码:

    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequence();
        System.out.println(stepSequence);
        for (Integer step : stepSequence) {
            sort(step);
        }
        System.out.println(Arrays.toString(array));
    }
    private void sort(int step) {
        // col:第几列,column的简称
        for (int col = 0; col < step; col++) {
            // 对[0,array.length)排序
            for (int begin = col+step; begin < array.length; begin+=step) {
                int  cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur-step);
                    cur-=step;
                }
            }
        }
    }

    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }