八大排序汇总及其稳定性_排序算法稳定性

public static void bubbleSort(int[] arr) {
        if(arr==null||arr.length<2)
            return;
        for(int e = arr.length-1; e > 0; e--){//控制比较的轮数，一共n-1轮
            for(int i = 0; i < e; i++){//3
                if(arr[i]>arr[i+1])
                    swap(arr,i,i+1);
            }
        }
    }

static void bubbleSort(int[] array) {
        int arrayLength = array.length;
        
        int preIndex = 0;
        int backIndex = arrayLength - 1;
        while(preIndex < backIndex) {
            preSort(array, arrayLength, preIndex);
            preIndex++;
            
            if (preIndex >= backIndex) {
                break;
            }
            
            backSort(array, backIndex);
            backIndex--;
        }
    }
    
    // 从前向后排序
    static void preSort(int[] array, int length, int preIndex) {
        for (int i = preIndex + 1; i < length; i++) {
            if (array[preIndex] > array[i]) {
                swap(array, preIndex, i);
            }
        }
    }
    
    // 从后向前排序
    static void backSort(int[] array, int backIndex) {
        for (int i = backIndex - 1; i >= 0; i--) {
            if (array[i] > array[backIndex]) {
                swap(array, i, backIndex);
            }
        }
    }
    
    static void swap (int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
​

public static void selectionSort(int[] arr) {
        if(arr==null||arr.length<2)
            return;
        for(int i=0;i<arr.length-1;i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                minIndex = arr[i] > arr[j] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

public static void insertionSort(int[] arr){
    if (arr == null || arr.length< 2){
        return;
        //e~e有序的
        //0~i想有序
    for(int i=1;i‹arr.length;i++){// 0～i做到有序
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]){
            //外层遍历到i位置，此时用i和i-1两位置进行比较，直到i前面的数都有序或者到位置为0
            swap(arr, j, j + 1);
        }
    }
}

public static void process(int[] arr, int L, int R) {
    if(L ==R){
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++]= arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[L + i] = help[i];//将临时数组的值赋值给原数组，注意是从L开始的
    }
}

public static int process(int[] arr, int i, int r) {
    if(i==r){
        return 0;
    }
    int mid = i +((r -i)>> 1);
    return process(arr, i, mid) + process(arr, mid + 1, r) + merge(arr, i, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
    int[] help = new int[r -L + 1];//开辟空间
    int i =0;
    int p1 = L;
    int p2=m+ 1;
    int res = 0;
    while (p1 <= m && p2 <= r){
        res+=arr[p1]< arr[p2]?(r-p2+1)*arr[p1]:0;//只要该值大于左边数组，那么该值右边的一定大于
        help[i++] = anr[p1] < arr[p2] ? arr[pl++]: arr[p2++];//当两值相等的时候必须先插入右边的，否则无法计算右边数组中到底有多少个大于该数的
    }
    while (p1<= m){
        help[i++] = arr[pl++];
    }
    while (p2 <= r) {
        help[i++] =arr[p2++];
    }
    for (i = 0;i < help.length;i++) {
        arr[L + i] = help[i];//会放到arr数组当中，方便下次递归使用
    }
    return res;
}

public static void quickSort(int[] arr) {
    if (arr == null || arr.length <2){
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}
​
// arr[1..r]排好序
public static void quickSort(int[] arr, int L, int R) {
    if(L< R){
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0]-1); // < 区
        quickSort(arr, p[1]+1, R); // > 区
    }
}
//这是一个处理arr[1..r]的函数
//默认以arr[r]做划分，arr[r]->p    <p  ==p     >p
//返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[o]res[1]
public static int[] partition(int[] arr, int L, int R) {
    int less=L-1；//<区右边界
    int more=R;//>区左边界
    while(L< more){ // L表示当前数的位置 arr[R] -> 划分值,当当前位置大于等于>区左边界时跳出
        if(arr[L]<arr[R]){//当前数‹划分值
            swap(arr, ++less, L++);
        }else if(arr[L]>arr[R]){//当前数>划分值
            swap(arr, --more, L);
        } else {
            L++;
         }
    }
    swap(arr, more, R);
    return new int[] { less + 1, more };
}

//取出最大元素之后执行此操作变成大根堆    
public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {//当前节点数值大于父节点位置
            swap(arr, index, (index - 1) /2);
            index = (index - 1)/2 ;
        }
    }

//大根堆什么也没有，此时不断进行插入排序，执行此操作
​
//某数a在index位置，将其往下移动
    public static void heapify(int[] arr, int index, int size) {//size为数组长度
        int left = index * 2 + 1;//左孩子位置
        while (left < size) {//判断孩子是否存在
            //只有当右孩子存在且大于左孩子时，才取右孩子作为最大值；
            //其余情况选左孩子，包括
            //  1.右孩子不存在
            //  2.右孩子存在但没左孩子大
            //largest记录最大值的位置
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            //比较父节点和大孩子之间谁大，记录下大的值的位置
            largest = arr[largest] > arr[index] ? largest : index;
            //如果父节点比较大，堆结构排好，退出
            if (largest == index) {
                break;
            }
            //孩子比较大，交换父和孩子的位置
            swap(arr, largest, index);
            //记录某数a的新位置
            index = largest;
            //记录处于新位置的某数a的左孩子
            left = index * 2 + 1;
        }
    }

   public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //将所有数字搞成大根堆
        //做法1：
//      for (int i = 0; i < arr.length; i++) {// O(N)
//          heapInsert(arr, i);// O(logN)
//      }
        //做法2：
        for (int i = arr.length-1; i >= 0 ; i--) {
            heapify(arr, i, arr.length);
        }
        int size = arr.length;
        //0位置上的数与heapsize最后一个数交换
        swap(arr, 0, --size);
        while (size > 0) {// O(N)
            //0位置上的数重新调整位置
            heapify(arr, 0, size);// O(logN)
            //0位置上的数与heapsize最后一个数交换,heapsize减小
            swap(arr, 0, --size);// O(1)
        }
    }
​

public static void main(String[] args) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.add(8);
    heap.add(3);
    heap.add(6);
    heap.add(2);
    heap.add(4);
    while (!heap.isEmpty()){
        System.out.println(heap.poll());
    }
}
//输出：2 3 4 6 8

public static class AComp implements Comparator<Integer>{
    //如果返回负数，认为第一个参数应该排在前面
    //如果返回正数，认为第二个参数应该排在前面
    //如果返回0，认为谁放前面都行
    @Override
    public int compare(Integer argo, Integer arg1) {
        return arg1 - arg0;
    }
}
​
public static void main(String[] args){
    PriorityQueue<Integer> heap = new PriorityQueue<>(new AComp());
    heap.add(6);
    heap.add(9);
    heap.add(3);
    heap.add(2);
    heap.add(10);
    while(!heap.isEmpty()) {
        System.out.println(heap.pol1());
    }
}

  public void sortedArrDistanceLessK(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        //k个数形成小根堆
        for (; index < Math.min(arr.length, k); index++) {
            //index < Math.min(arr.length, k)进行的操作是避免传的参数不合适造成程序的无法正常运行
            heap.add(arr[index]);
        }
        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);//加一个数
            arr[i] = heap.poll();//弹出一个最小值
        }
        while (!heap.isEmpty()) {//依次弹出k个最小值
            arr[i++] = heap.poll();
        }
    }
​

  // only for no-negative value
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }
    //计算最大的十进制位是第几位
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);//寻找数组中最大的数
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;//自动整除，因为max是int
        }
        return res;
    }
​
    public static void radixSort(int[] arr, int begin, int end, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
​
        int[] bucket = new int[end - begin + 1];
        //digit多少哥十进制位，也代表入桶出桶的次数
        for (int d = 1; d <= digit; d++) {
            int[] count = new int[radix];
            //用于记录当前位上等于0,...,等于9的各有多少个数
            for (i = begin; i <= end; i++) {
                j = getDigit(arr[i], d);//确认当位上的数是多少
                count[j]++;//等于该位上的数，统计加1
            }
            //用于记录当前位上小于等于0,...,小于等于9的各有多少个数
            //同时也记录了当前位上等于0,...,等于9的数组最后一个数出桶后的位置
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for (i = end; i >= begin; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];//出桶后的位置上放该数
                count[j]--;//该桶上的数减一
            }
            for (i = begin, j = 0; i <= end; i++, j++) {
                //把bucket的数组导入arr中，相当于保留了这次桶排序
                arr[i] = bucket[j];
            }
        }
    }

​

​

public class Test {
    public static void quickSort(int[] arr, int 1, int r) {
        if(1 ==r){
            return;
        }
        if (1 >r - 60) {//插入排序
            在arr[1..r]插入排序
            O（Nへ2）小样本量的时候，跑的快
            return;
        }
        swap(arr, 1 + (int) (Math.random() * (r - 1 + 1)), r);//快速排序
        int[] p = partition(arr, 1, r);
        quickSort(arr, 1, p[0] - 1); //‹ 区
        quickSort(arr, p[1] + 1, r); // > 区
    }
}