【排序算法总结】

1. 稳点与非稳定排序

• 不稳定的：快排、堆排、选择
• 原地排序：快排也是
• 非原地排序：归并 和三个线性时间排序：桶排序 ，计数，基数

2. 冒泡排序

• 时间复杂度 O(n*n)
• 空间复杂度 O(1)
• 稳定

public class ReviewToo {
    //1.冒泡排序 时间复杂度 O(n*n)  空间复杂度 O(1) 稳定
    public int[] BubbleSort(int[] a) {
        int temp;//空间复杂度的体现
        boolean flag;
        o:
        for (int i = 1; i < a.length; i++) {
            flag = false;
            for (int j = 0; j < a.length - i; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            if (flag == false) {
                break o;
            }
        }
        return a;
    }

3. 简单选择排序

• 时间复杂度 O(n*n)
• 空间复杂度 O(1)
• 不稳定

    //2.简单选择排序 时间复杂度 O(n*n)  空间复杂度 O(1) 不稳定
    public int[] simpleSelectSort(int[] a) {
        int temp, min;//空间复杂度的体现
        for (int i = 0; i < a.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            if (min != i) {
                temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
        return a;
    }

4. 直接插入排序

• 时间复杂度 O(n*n)
• 空间复杂度 O(1)
• 稳定

    //3.直接插入排序 时间复杂度 O(n*n)  空间复杂度 O(1)  稳定
    public int[] straightInsertionSort(int[] a) {
        //第一个元素是有序表 后面的是无序表 从后往前插
        for (int i = 1; i < a.length; i++) {
            int value = a[i];//要插入的元素
            int index = i - 1;//要插入的位置
            while (index >= 0 && value < a[index]) {
                if (value < a[index]) {
                    a[index+1]=a[index];
                    //索引前移继续找插入位置
                    index--;
                }
            }
            //循环结束找到了插入位置
            a[index+1]=value;
        }
        return a;
    }
 }

5. 快排

• 时间复杂度 O(n* log n)
• 空间复杂度 O(log n)
• 不稳定

//4.快排;
// 时间复杂度 O(n* log n)  空间复杂度 O(log n)  不稳定
public class FastSort {
    public static void quikSort(int[] arr, int left, int right) {
        // 1.快排终止条件（递归出口）：只有一个元素或者无元素，不进行快排
        if (left >= right) {
            return;
        }
        // 2.选取基准元素：我们以数组左边的元素为基准元素
        int num = arr[left];
        // 定义首尾指针
        int start = left;
        int end = right;
        // 3.指针移动条件：指针未相交
        while (start < end) {
            // 先移动右边的指针（因为选取的是最左边的元素作为基准元素）
                //每次找出第一个比基准元素小的 end停到那
            while (start < end && arr[end] >= num) {
                end--;
            }
            // 再移动左边的指针
            while (start < end && arr[start] <= num) {
                start++;
            }

            // 两指针终止但没相交，交换元素
            if (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
        // 4.循环结束两指针相交，排序结束，将基准元素放入指针相交位置
        arr[left] = arr[start];
        arr[start] = num;
        // 5.继续递归：分别对基准元素左右两边的元素进行快排 此时基准元素的左边全部小于它本身，右边全部大于它本身
        //快排左边
        quikSort(arr, left, start - 1);
        //快排右边
        quikSort(arr, start + 1, right);
    }
    //主函数
    public static void main(String[] args) {
        int[] arr = {34, 1, 5, -2, 0, 35, 36, 38};
        //初始的left=0；
        //right=arr.length-1;
        quikSort(arr, 0, arr.length - 1);
        for (int value : arr) {
            System.out.print(value+" ");
        }
    }
}

6. 堆排

//5.堆排;
public class Re {
    public static void heapSort(int[] arr) {
        int len = arr.length;
        int[] top = new int[100];
        for (int i = 0; i < top.length; i++) {
            top[i] = arr[i];
        }
        buildHeap(top);
        for (int i = len-1; i >=0 ; i--) {
            swap(arr,0,i);
            len--;
            heapify(arr,0,len);
        }
    }

    public static void buildHeap(int[] arr) {
        int len = arr.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    public static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min = i;
        if (left < len && arr[min] > arr[left]) {
            min = left;
        }
        if (right < len && arr[min] > arr[right]) {
            min = right;
        }
        if (min != i) {
            swap(arr, min, i);
            heapify(arr, min, len);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

7. 归并

//6.归并排序;
import java.util.Arrays;
public class MergeSort {
    //一、拆分部分
    public static void split(int[] arr,int left,int right,int[] temp){
        //递归拆分
        if (left<right){
            int mid=(left+right)/2;
            //左递归分解
            split(arr, left, mid, temp);
            //右递归分解
            split(arr, mid+1, right, temp);
            //合并
            merge(arr,left,right,mid,temp); //这么理解就像递归就是重复干一件事 你调用执行就可
            //上面 先左递归合并 再右递归合并
        }
    }
    //二、合并部分
    /**
     * @param arr   要进行排序的初始数组
     * @param left  左序列数组的初始索引
     * @param right 右序列数组的初始索引
     * @param mid   左序列和右序列的交接地方 中间索引
     */
    public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
        int i = left;//初始化i，作为左序列的初始索引
        int j = mid + 1;//初始化j，作为右序列的初始索引 mid是向下取整得来的
        int index = 0;//temp数组的当前索引
        //1.左右两边序列按照规则填充到temp数组 直到有一边处理完毕
        //循环条件 两边的数据均为处理完
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) { //左元素<=右 就把左里面的首位填充到temp
                temp[index] = arr[i];
                i++;//i后移
                index++;//index后移
            } else {//反之就填充右里面的首位
                temp[index] = arr[j];
                j++;
                index++;
            }
        }
        //当while循环结束 就有其中一边先处理完毕
        //2.把另一边中剩下的的数据直接依次填充到temp数组
            //满足哪个就去哪个循环进行填充
        while (j <= right) {
            temp[index] = arr[j];
            index++;
            j++;
        }
        while ((i <= mid)) {
            temp[index] = arr[i];
            index++;
            i++;
        }
        //3.temp数组拷贝到arr中
        //只有最后一次拷贝是把整个temp拷贝到arr数组中 前几次都是拷贝temp中的一部分
        //因为前几次的合并没有占满temp数组
        index=0;//temp索引归0；
        int tempLeft=left;
//        System.out.println("tempLeft="+tempLeft+" "+"right="+right);
            //第1次合并 tempLeft=0,right=1;
            //第2次合并 tempLeft=2,right=3;
            //第3次合并 tempLeft=0,right=3;
            //第4次合并 tempLeft=4,right=5;
            //第5次合并 tempLeft=6,right=7;
            //第6次合并 tempLeft=4,right=7;
            //第7次合并 tempLeft=0,right=7;//最后一次合并
        while (tempLeft<=right){
            arr[tempLeft]=temp[index];
            tempLeft++;
            index++;
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{8, 4, 5, 7, 6, 2, 3, 9};
        int[] temp=new int[arr.length];
        split(arr,0, arr.length-1,temp);
        System.out.println(Arrays.toString(arr));

    }
}