目录
排序
排序的概念：
假设含有n个记录的序列为{R1,R2,R3,···,Rn}，其相应的关键字分别为{K1,K2,K3,···Kn}，需确定1,2,3,···,n的一种排列P1,P2,···,Pn，使其相应的关键字满足Kp1 <= Kp2 <= Kp3 <= ···· <= Kpn非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列{Rp1,Rp2,····,Rpn}。
排序稳定性：
假设Ki = Kj( 1 <= i <= n, 1 <= j <= n, i != j)，且在排序前的序列中Ri领先于Rj，则称所用的排序方法时稳定的；反之，若可能使得排序后的序列中Rj领先于Ri，则称所用的排序算法是不稳定的。
也就是说如果两元素相同排序前啥位置排序后还是啥位置该排序就稳定，反之不稳定。
内排序：
内排序是在排序的整个过程中，将排序所有记录全部放置在内存中。
外排序：
外排序是由于排序的记录个数太多，不能同时放在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。
常见排序如下图：
以下排序都是实现从小到大。
冒泡排序
原理：两两比较相邻记录的关键字，如果反序就交换直到没有反序记录为止。
实现思路：
- 外循环实现比较趟数。
- 内循环实现从末尾找到最小值向前排。
如此每一趟都可以将一个最小值排在前面。
代码已优化点：
- 使用了一个falg标记，如果该趟没有交换证明数组已经有序，直接结束。
- 使用
j > i作为第二层循环的结束条件而不是j > 0减少了循环次数。
时间复杂度：O(N^2) 。
空间复杂度：O(1)。
稳定性：稳定。
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; i++) {
boolean flag = false;
for (int j = array.length - 1; j > i; j--) {
if(array[j] < array[j - 1]){
//交换
int tmp = array[j - 1];
array[j - 1] = array[j];
array[j] = tmp;
flag = true;
}
}
if(!flag){
break;
}
}
}
选择排序
原理：就是通过n - i 次关键字之间的比较，从n - i + 1 个记录中选出关键字最小的记录，并和第 i （1 <= i <= n）个记录交换。
实现思路：
- 外循环控制每次最小值放入的位置。
- 内循环找到当前的最小值下标。
- 出内循环将最小值与当前应放入位置交换。
每一次都可以挑选一个最小值出来。与冒泡排序有相似之处，但是冒泡相邻比较交换，选择排序是每次交换最小值。
时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：不稳定。
// 选择排序
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if(array[j] < array[minIndex]){
minIndex = j;
}
}
int tmp = array[minIndex];
array[minIndex] = array[i];
array[i] = tmp;
}
}
直接插入排序
原理：直接插入排序的基本操作就是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录增1的有序表。
实现思路：
- 外部使用循环控制当前填入前方有序数组的值tmp。
- 内部循环从当前前一个下标开始往回遍历，遇到比tmp大的值就往后覆盖，否则就出循环（因为前面已经是有序的了）。
- 最后一定要将 j+1 下标置为tmp（因为出第二层循环时要么为-1要么当前j下标值小于等于tmp）。
时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：稳定。
//直接插入排序
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
希尔排序
原理：将大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列中分别进行直接插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序。
实现思路：
- 在希尔排序中循环调用修改后的直接插入排序。
- gap代表增量，相当于 i 下标与 i + gap * n下标的值为一组。
- 对每组进行直接插入排序。
时间复杂度：O(n^1.3 )至 O( n^1.5)之间。
空间复杂度：O(1)。
稳定性：不稳定。
// 希尔排序
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}
堆排序
原理：将待排序的序列构造成一个大根堆。此时，整个序列的最大值就是堆顶元素。将它移走（其实就是将堆顶元素与堆尾元素交换，此时末尾元素就是最大值），然后将剩余的n - 1个序列重新构造成一个大根堆，这样就可以得到n个元素中的次大值。如此反复操作，便能得到一个有序序列。
实现思路：
- 根据排序需求（升序实现大根堆，降序实现小根堆），实现堆。
- 每次将堆顶元素放末尾，将剩余元素再变为堆。
时间复杂度：O(N*logN)。
空间复杂度：O(1)。
稳定性：不稳定。
// 堆排序
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
//实现大根堆
private static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array, int parent, int length) {
int child = 2 * parent + 1;
while (child < length) {
if(child + 1 < length && array[child] < array[child+1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array, parent, child);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
//交换函数
private static void swap(int[] array, int x, int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
归并排序
原理：假设初始序列含有n个记录，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2向上取整个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2路归并排序。
实现思路：
- 分解逻辑：将递归结束条件变为左下标大于右下标达到每个子序列只有1个元素。
- 合并逻辑：因为两个子序列本身是有序的了，只要将两个序列从左到右的最小值依次放入临时数组，最后有一个数组剩余元素直接放入即可。（注意临时数组返回给目标数组时开头不是0下标开始）
时间复杂度：O(N*logN)。
空间复杂度：O(N)。
稳定性：稳定。
//归并排序
public static void mergeSort(int[] array) {
mergeSortTmp(array,0,array.length-1);
}
private static void mergeSortTmp(int[] array,int left,int right) {
if(left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSortTmp(array,left,mid);
mergeSortTmp(array,mid+1,right);
//分解完毕
// 合并
merge(array,left,mid,right);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int s2 = mid+1;
while (s1 <= mid && s2 <= right) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= mid) {
tmp[k++] = array[s1++];
}
while (s2 <= right) {
tmp[k++] = array[s2++];
}
//可以保证tmp数组 是有序的
for (int i = 0; i < k; i++) {
array[i+left] = tmp[i];
}
}
快速排序
原理：通过一趟排序将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
时间复杂度：O(N*logN)至O(n^2)。
空间复杂度：O(logN)至O(N)。
稳定性：不稳定。
//快速排序
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int pivot = partition(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
while (left < right) {
while (left < right && array[right] >= tmp) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= tmp) {
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}