### 排序算法
#### 归并排序
// 归并排序
public static void mergeSort(int[] arr){
// 创建一个临时数组，用来存储合并之后的数组
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] a, int[] b, int left, int right){
// 当left==right的时，已经不需要再划分了
if (left < right){
int middle = (left+right)/2;
internalMergeSort(a, b, left, middle); //左子数组
internalMergeSort(a, b, middle+1, right); //右子数组
mergeSortedArray(a, b, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
// 这里的核心就是合并两个有序数组，谁大放进新的数组
while (i <= middle && j <= right){
if (arr[i] <= arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
// 左边的还有剩余
while (i <= middle){
temp[k++] = arr[i++];
}
// 右边的还有剩余
while (j <= right){
temp[k++] = arr[j++];
}
// 把数据复制回原数组
for (i=0; i
=1; delta/=2){ //对每个增量进行一次排序
for (int i=delta; i=delta && arr[j]=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在，lastIndex 是最后一个节点的索引，不是其父节点的索引，要注意
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex arr[j]) {
min = j;
}
}
// 把最小的与 index 位置元素交换
if (min != index) {
temp = arr[index];
arr[index] = arr[min];
arr[min] = temp;
}
}
}
#### 冒泡排序
设现在要给数组arr[]排序，它有n个元素。
1.如果n=1：显然不用排了。
2.如果n>1：
1)我们从第一个元素开始，把每两个相邻元素进行比较，如果前面的元素比后面的大，那么在最后的结果里面前者肯定排在后面。所以，我们把这两个元素交换。然后进行下两个相邻的元素的比较。如此直到最后一对元素比较完毕，则第一轮排序完成。可以肯定，最后一个元素一定是数组中最大的（因为每次都把相对大的放到后面了）。
2)重复上述过程，这次我们无需考虑最后一个，因为它已经排好了。
3)如此直到只剩一个元素，这个元素一定是最小的，那么我们的排序可以结束了。显然，进行了n-1次排序。
上述过程中，每次（或者叫做“轮”）排序都会有一个数从某个位置慢慢“浮动”到最终的位置（画个示意图，把数组画成竖直的就可以看出来），就像冒泡一样，所以，它被称为“冒泡排序法”。
public static void bubbleSort(int[] arr) {
int temp = 0;
for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}//loop j
}//loop i
}// method bubbleSort
#### 快速排序
- 快排的思想很简单，从左到右依次往中间前进
- 复杂度要记住为 O(n logn)
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //枢轴记录
while(low=pivot) --high;
arr[low]=arr[high]; //交换比枢轴小的记录到左端
while(low < high && arr[low]<=pivot) ++low;
arr[high] = arr[low]; //交换比枢轴小的记录到右端
}
//扫描完成，枢轴到位,注意这时候 low 已经前进到中间的位置了
arr[low] = pivot;
//返回的是枢轴的位置
return low;
}
#### 插入排序
- 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
- 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
- 重复上述过程直到最后一个元素被插入有序子数组中。
- 排序完成。
public static void insertionSort(int[] arr){
// 注意 i = 1 开始排序的，即从第二个元素开始
for (int i=1; i0 ; --position){
// 如果比前面的元素小，前面的元素就自动向后面退一位
if (arr[position-1] > value){
arr[position]=arr[position-1];
}
// 如果比前面的元素大，前面的元素不用动，这次循环结束
else{
break;
}
}
// 将未排序的元素插入到指定的位置
arr[position] = value;
}
}
