# 排序算法

# 尽可能的问

你了解哪些排序算法，它们的时间复杂度是多少？

O(n^2)
- 冒泡排序
- 插入排序
- 选择排序
O(nlogn)
- 快排
- 归并排序
O(n)
- 桶排序
- 计数排序
- 基数排序

算法除了关注时间复杂度以外通常还需关注哪些算法特征？

时间复杂度
- 最好、最快、平均时间复杂度
- 比较次数、交换次数
空间复杂度（系数、常数、低阶）
- 是否是原地排序
是否基于比较
稳定性
有序度和逆序度

# 冒泡排序

时间复杂度

# 插入排序

分为已排序区间和未排序区间，将未排序区间中的数选一个插入到已排序区间中

代码实现：

// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
    if (n <= 1) return;
    for (int i = 1; i < n; i++) {
        // 在未排序区间拿到当前要排序的数
        int value = a[i];
        // 查找插入的位置
        // 初始时，选择左侧第一个元素为已排序区间（单个元素当然有序），因此未排序区间是已排序区间+1
        // 所以已排序区间为i-1，将遍历前i-1个元素，将第i个元素插入到其中即可
        int j = i-1;
        for (; j >= 0; j--) {
            if (a[j] > value) {
                // 数据移动
                a[j+1] = a[j];  
            } else {
                break;
            }
        }
        // 插入数据
        a[j+1] = value;
    }
}

# 归并排序

算法应用：

求逆序对
求交换次数
我们部门要排队唱歌，大家乱哄哄的挤在一起，现在需要按从低到高的顺序拍成一列，但每次只能交换相邻的两位，请问最少要交换多少次？如：3, 1, 2, 5, 6, 4，交换次数为4。最小交换次数即是逆序对数目
求数组单调和

# 代码实现

实现1（递归）:

public class MergeSort {
    public void main(int[] nums){
        int n = nums.length;
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[n];
        sort(nums, 0, n-1, temp);
    }
    
    private void sort(int[] nums,int left,int right,int []temp){
        if (left < right) {
            int mid = left + (right - left)/2;
            sort(nums,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(nums,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(nums,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    
    private void merge(int[] nums,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }
        //将左边剩余元素填充进temp中
        while (i <= mid) {
            temp[t++] = nums[i++];
        }
        while (j<=right) {//将右序列剩余元素填充进temp中
            temp[t++] = nums[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            nums[left++] = temp[t++];
        }
    }
}

实现2（递归）:

public class MergeSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }
}

迭代实现：

public static void mergeSortIteration(int[] arr, int len) {
	int start, mid, end;
	for(int i = 1; i < len; i *= 2) {
		start = 0;
		// 两两归并，直到后一个子数组不存在
		while(start + i < len) {
			mid = start + i - 1;
			end = mid + i < len ? mid + i : len - 1;
			merge(arr, start, mid, end);
			start = end + 1; // 归并下一对数组
		}
	}
}

# 堆排序

堆的定义：

请跳转到算法基础章节（堆）了解。

为什么快排的性能比堆排序的性能好？

快排的数据访问方式较优。快排是顺序访问，有利于cpu缓存；而堆排序是跳着访问。
快排的数据交换次数要少于堆排序。（并且有序的数据，在建堆的过程中会变成无序。）

堆排序的优势有哪些？

稳定的时间复杂度

有哪些源码中使用堆排序来实现排序函数？

时间空间复杂度

时间 O(nlogn)
空间 O(1)

堆排序的步骤有哪些？

建堆
排序

对应代码实现：

# 快速排序

题目： 215. 数组中的第K个最大元素（此题最优解为快速选择算法）

# 计数排序

计数排序资料 (opens new window)

# 排序资料

https://www.bilibili.com/video/av63851336 https://www.bilibili.com/video/av25136272 https://www.cnblogs.com/onepixel/p/7674659.html

← 字符串算法搜索算法 →