归并排序
这里用递归实现了归并排序，左边排序->右边排序->让其整体有序。
让其整体有序的过程中使用了排外序的方法。即构造一个新的数组，比较对i, j所指向的数字进行大小比较，如果arr[i] >arr[j]，则将arr[i] 的值复制到新数组中，i + 1，j 不变。这样依次遍历，直到 i 或 j 到达临界点，跳出循环。将剩余部分直接拷贝到新数组中。
根据 master 公式，归并排序的时间复杂度为 O(logN * N），空间复杂度为O(N)。
归并排序的实质
代码实现：
class Sort{
public:
static void merge(int arr[],int L,int mid,int R){
int i = L;
int j = mid + 1;
int k = 0;
int *temp_arr = new int(R - L + 1);
for( ; i <= mid && j <= R; ){
temp_arr[k++] = arr[i] > arr[j] ? arr[i++] : arr[j++];
}
while(i <= mid){
temp_arr[k++] = arr[i++];
}
while(j <= R){
temp_arr[k++] = arr[j++];
}
for(i = L,k = 0; i <= R; i++,k++){
arr[i] = temp_arr[k];
}
delete temp_arr;
}
static void mergeSort(int arr[],int L,int R){
if(L == R)
return;
int mid = L + ((R - L) >> 1);
cout << mid << endl;
mergeSort(arr,L,mid);
mergeSort(arr,mid+ 1,R);
merge(arr,L,mid,R);
}
static void mergeSort(int arr[],int length){
if(arr == NULL || length <= 0)
return;
mergeSort(arr,0,length - 1);
}
};
例题：
1. 小和问题：一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16
static int merge(int arr[],int L,int mid,int R){
int i = L;
int j = mid + 1;
int k = 0;
int res = 0;
int* temp_arr = new int(R - L + 1);
for( ; i <= mid && j <= R; ){
res += arr[i] < arr[j] ? arr[i] * (R - j + 1) : 0;
temp_arr[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
}
while(i <= mid){
temp_arr[k++] = arr[i++];
}
while(j <= R){
temp_arr[k++] = arr[j++];
}
for(i = L,k = 0; i <= R;){
arr[i++] = temp_arr[k++];
}
delete temp_arr;
return res;
}
static int mergeSort(int arr[],int L,int R) {
if( L == R )
return 0;
int mid = L + ((R - L) >> 1);
return mergeSort(arr,L,mid) + mergeSort(arr,mid + 1,R) + merge(arr,L,mid,R);
}
static int smallSum(int arr[],int length){
if(arr == NULL || length == 0)
return 0;
return mergeSort(arr,0,length - 1);
}
2.逆序对问题 在一个数组中，左边的数如果比右边的数大，则折两个数 构成一个逆序对，请打印所有逆序 对.
static int merge(int arr[],int L,int mid,int R){
int i = L;
int j = mid + 1;
int k = 0;
int res = 0;
int* temp_arr = new int(R - L + 1);
for( ; i <= mid && j <= R; ){
// res += arr[i] < arr[j] ? arr[i] * (R - j + 1) : 0;
// temp_arr[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
if(arr[i] > arr[j]){
int p = j;
for( ; p <= R; p++)
cout << arr[i] << " " << arr[p] << endl;
temp_arr[k++] = arr[i++];
}
else{
temp_arr[k++] = arr[j++];
}
}
while(i <= mid){
temp_arr[k++] = arr[i++];
}
while(j <= R){
temp_arr[k++] = arr[j++];
}
for(i = L,k = 0; i <= R;){
arr[i++] = temp_arr[k++];
}
delete temp_arr;
return res;
}
static int mergeSort(int arr[],int L,int R) {
if( L == R )
return 0;
int mid = L + ((R - L) >> 1);
// return mergeSort(arr,L,mid) + mergeSort(arr,mid + 1,R) + merge(arr,L,mid,R);
mergeSort(arr,L,mid);
mergeSort(arr,mid + 1, R);
merge(arr,L,mid,R);
}
static int inversion(int arr[],int length) {
if(arr == NULL || length == 0)
return 0;
return mergeSort(arr,0,length - 1);
}
堆
堆结构的实质是用数组实现的完全二叉树结构，可分为大根堆与小根堆。
大根堆：在完全二叉树中，每棵子树的最大值都在根节点；
小根堆：在完全二叉树中，每棵子树的最小值都在根节点。
根据完全二叉树的性质，设父节点的下标为 i ，如果它的两个孩子都存在，则左孩子的下标为 i * 2 + 1，右孩子的下标为 i*2 +2.
设子节点的下标为i，则父节点的下标为 (i - 1）/ 2.
堆结构主要包括
数据成员 heapSize：堆的大小
成员函数 heapInsert()：根据一定的条件向上调节节点。O(logN)
成员函数 heapify（）：根据一定的条件向下调节节点。O(logN)
堆的增大与减小与数组本身的长度没有关系，只与heapSize有关。
优先级队列结构就是堆结构（小根堆）。
class HeapSort{
public:
static void heapInsert(int arr[],int heapSize,int index){
while(arr[index] > arr[(index - 1) / 2]){
swap(arr[index],arr[(index - 1) / 2]);
index = (index - 1) / 2;
}
}
static void heapify(int arr[],int heapSize,int index){
int L = index * 2 + 1;
while(L < heapSize){
int largest = heapSize > L + 1 && arr[L] < arr[L + 1] ? L + 1 : L;
largest = arr[index] > arr[largest] ? index : largest;
cout << "largest:" << largest << endl;
cout << "index:" << index <<endl;
if( largest == index)
break;
swap(arr[index],arr[largest]);
index = largest;
L = index * 2 + 1;
}
}
static void addNum(int arr[],int heapSize,int new_num){
arr[heapSize++] = new_num;
heapInsert(arr,heapSize,new_num);
}
static void altNum(int arr[],int heapSize,int index,int new_num){
arr[index] = new_num;
heapInsert(arr,heapSize,index);
heapify(arr,heapSize,index);
}
static void heapSort(int arr[],int length){
if(arr == NULL || length <= 1)
return;
int i = 0;
for( ; i < length; i++){
heapInsert(arr,length,i);
}
int heapSize = length;
while(heapSize > 0){
swap(arr[0],arr[--heapSize]);
heapify(arr,heapSize,0);
}
}
};
堆排序：
1. 将数组调整为大根堆
2. 将堆的最大值（根节点）与末尾的值进行交换 -> 减小heapSize -> 将数组调整为大根堆
3. heapSize = 0 排序结束
在上面的heapSort() 中，第一步将数组调整为大根堆的时间复杂度为O(N*logN)，后两步的时间复杂度也是O(N*logN),所以最终堆排序的时间复杂度为O(N*logN).
实际上heapSort()中，第一步还可以继续优化，上面采用的是自顶向下的建堆方式，优化的算法采用的是自底向上的建堆方式，即从（heapSize - 1）开始，依次倒序遍历数组，同时执行heapigy()函数，知道heapSize = 0。该算法的时间复杂度为O(N),证明如下：
若存在一个节点个数为N的完全二叉树，则最底层的节点个数为N / 2, 倒数第二层的节点个数为 N / 4......，
所以 该算法的常数时间的操作为 T(N) = N / 2 + N / 4 * 2 + N / 8 * 3 + ......
而 2T(N) = N / 2 * 2 + N / 2 * 2 + N / 4 * 3 + ......
所以 T(N) = N + N / 2 + N / 4 + ...... = N * (1 - 1 / 2) / (1 - 1 / 2) = N * ( 1 / 2) ^ (N - 1)
所以使用该种方法建立大根堆的时间复杂度为O(N).
在排序过程中，将数组调整为大根堆共有两种方式：
自顶向下的建堆：依次读入数组的值，将值看作新加入堆的值，然后使用heapInsert() 函数向上调节节点到它应该在位置,时间复杂度为O(N*logN)；
自底向下的建堆：时间复杂度为O（N）。
堆排序扩展题目
1. 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元 素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。
解题思路：首先建立一个小根堆，将前k + 1个数加入小根堆，从小根堆中选出最小的数放在0位置；再将第k+ 2个数放入小根堆，将现在小根堆中最小的数放在1位置。。。。。。该算法的时间复杂度为O(N*logk)。
注：可以使用priority_queue来简化。
public void sortedArrDistanceLessK(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
for (; index < Math.min(arr.length, k); index++) {
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; i++, index++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
快速排序
首先介绍荷兰国旗问题
问题一
给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的 数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
问题二
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放 在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度 O(N)
解决荷兰国旗问题的思路是：分别定义 less 和 more 来划分大于num与小于num在数组中的范围,用index来遍历数组，初始时 less = -1，more = arr.length,index = 0。
1. 如果arr[index] > num，more--,交换arr[more] 与arr[index];
2. 如果arr[index] < num,less++，index++;
3. 如果arr[index] = num,,index++.
public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}
荷兰国旗问题的算法实现就是快速排序中最重要的部分。
经典快排的实现过程：
1. 将arr[length - 1] 作为划分值，然后通过荷兰国旗问题把数组划分为3个部分：左侧< 划分值；右侧 > 划分值；中间= 划分值。
2. 将arr[length - 1] 的值与arr[index] > 划分值的前一个数做交换。
3. 令index = 划分值的位置 - 1，递归执行上述过程；令index = 划分值的位置+1，递归执行上述过程。
经典快排的时间复杂度为O（N^2）;
对这个算法可以做出改进。
改进一：
与经典快排的实现过程基本相同，但在做完交换后进行，令index = less，递归；index = more，递归。
在最差情况下，该算法的时间复杂度同样为O（N^2）.
划分值越接近两侧，时间复杂度越高；划分值越接近中间，划分值越低。
在最好的情况下，该算法的时间复杂度为O(N);
改进二：
1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分 成三个部分： 左侧<划分值、中间==划分值、右侧>划分值
2）对左侧范围和右侧范围，递归执行
3）时间复杂度为O(N*logN)
在这种情况下，取到任何划分值的可能性都是随机且相等的。最好情况下的时间复杂度为O（N* logN），最差情况下为O(N^2)，经过复杂的数学推演（真的很复杂，都看不懂），时间复杂度可以收敛为O(N*logN).
对于空间复杂度，最差情况下为O(N),最好情况下为O（logN）,收敛后为O(logN).
class Sort{
public:
static void quickSort(int arr[],int length){
if(arr == NULL || length <= 1){
return;
}
quickSort(arr,0,length - 1);
}
static void quickSort(int arr[],int L,int R)
{
if(L == R)
return;
int temp = arr[rand()%(R - L + 1)];
int num = arr[temp];
int less = L - 1;
int more = R;
int i = L;
for(; i < more;){
if(arr[i] < num){
swap(arr[++less],arr[i++]);
}
else if(arr[i] > num){
swap(arr[--more],arr[i]);
}
else{
i++;
}
}
swap(arr[temp],arr[less + 1]);
quickSort(arr,0,less);
quickSort(arr,more,R);
}
};
