数据结构与算法-排序算法

1 使用递归的方式求最大值

public class GetMaxTest {
    public static int getMax(int[] arr){
        return process(arr,0,arr.length);
    }

    // arr[L..R]范围上的最大值
    public static int process(int[] arr,int L,int R){
        // arr[L..R]范围上只有一个数 直接返回 base case
        if (L == R) {
           return arr[L];
        }
        // 中点 
        // 如果采用这种写法
        // int mid = (L + R) / 2 
        // 存在的问题是 如果 L 和 R 比较大的时候可能会出现溢出的情况 
        int mid = L + ((R - L) >> 1);
        int leftMax = process(arr,L,mid);
        int rightMax = process(arr,mid + 1 ,R);
        return Math.max(leftMax,rightMax);// 时间复杂度 O(1)
    }
	public static void main(String[] args) {
	       int[] arr = {10,20,35,6,8};
	       System.out.println(getMax(arr));
	   }
}

递归将整个函数的调用过程 调用过程

如何在CSDN博客中插入公式和各种符号

类似二叉树的后续遍历
递归行为和递归行为时间复杂度的估算
master公式 :

$T(n)=a\times T(\frac{n}{b})+O(n^d)$
$T(n)$ : 母问题的规模
$a$ : 调用次数
$b$: 子问题的规模
$O(n^d)$ : 除了子问题之外的时间复杂度

在此问题中 $T(n)$ 公式为 :

$a=2$
$b=2$
$d=0$
$T(n)=2\times T(\frac{n}{2})+O(1)$

中间加一个打印 额外的时间复杂度就变成了 $O(n)$

$lo{g}_b^a$ > d 复杂度为$O(n^{lo{g}_b^a}$)

$lo{g}_b^a$ = d 复杂度为$O(n^d$$\times$logn)

$lo{g}_b^a$ < d 复杂度为$O(n^d$)

此递归的时间复杂度为 $O(n^{lo{g}_2^2})$ 即为 $O(n)$

2 时间复杂度

• 常数时间的操作
  一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作
  时间复杂度作为一个算法流程中,常数操作数量的一个指标,常用$O$来表示,具体来说,需要对一个算法的流程非常熟悉,然后去写这个算法的流程中,发生了多少常数操作,从而总结出常数操作数量的表达式,
  在表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果为 $f(n)$ 那么时间复杂度为$O(f(n))$

  评价一个算法流程的好坏,先看时间复杂度指标,然后再分析不同样本下的实际运行时间,也就是"常数项时间"

3 选择排序和冒泡排序的时间复杂度分析

选择排序
coding

public class SelectionSortTest {
    public static void selectionSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        // 保证 i - N-1 上的数最小
        for (int i = 0; i < arr.length - 1 ; i++) {
            int minIndex = i;
            // 在 i   - (N - 1)上找最小值的下标
            for (int j = i + 1; j < arr.length;j++){
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            // 可能会出现 i == index
            swap(arr,i,minIndex);
        }
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        // 使用下面这种交换方法 i 和 j 不能相等
       /* arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];*/
    }
}

冒泡排序
coding

public class BubbleSortTest {
    public static void bubbleSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        // 0 - (N - 1) 范围上相邻两个数交换 放在最后  时间复杂度为 O(N^2)
        for (int  e = arr.length - 1; e > 0; e--){
            // 从0开始,前一个数比后一个数大  就交换
            for (int j = 0;j < e;j++){
                if (arr[j] > arr[j + 1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
    
    // 可以交换的前提是 i != j 否则会将值修改成 0
    public static void swap(int[] arr,int i,int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
    
}

异或运算

相同为0,不同为1

异或运算的性质

0 ^ N   = N
N ^ N = 0

异或运算满足交换律和结合律

a ^ b ^ c = a ^ c ^ b

异或运算可以理解为无进位相加

交换两个数使用异或的方法

// 自己跟自己异或是 0
// 自己跟 0 异或是自己 
// 交换的前提是在内存中是两块不同的区域
int a = 10;
int b = 20;
a = a ^ b;
b = a ^ b;// a^b^b a^0 a
a = a ^ b; // a = a ^ a ^ b 0 ^ b b

关于异或运算的算法
1 已知在一个数组中,只有一个数出现了奇数次,其它数都出了偶数次,如何找到这个数
coding

public static int findOccurOddTimes1(int[] arr) {
    int eor = 0;
    for (int ele : arr) {
        eor ^= ele;
    }
    return eor;
}

2 一个数组中,有两个数字出现了奇数次 这两个数字不相同 其他数都是出现了偶数次 如何找出这两个数字

/**
 * 一个数组中,有两个数字出现了奇数次 这两个数字不相同 其他数都是出现了偶数次 如何找出这两个数字
 */
public static int[] findOccurOddTimes2(int[] arr) {
    int[] retArr = new int[2];
    int eor = 0;

    for (int i = 0; i < arr.length; ++i) {
        eor ^= arr[i];
    }

    // eor 就是 a ^ b 因为 a和 b 不相等 所以 eor一定不是0 一定有一位是1
    // a 和 b 一定有一位上 a 是 0 b 是 1  所有的这些数可以分成这一位上是0和这一位上不是 0
    // 提取出数据最右边的 1 一个数字 与 它按位取反+1 就会提取出最右侧的1
    int rightNumber = eor & (~eor + 1);
    int onlyOne = 0;
    for (int cur : arr) {
        // 数组中所有这一位上是0的数与 onlyOne作与运算 最终得到的结果就是 A或B中的其中一个
        if ((cur & rightNumber) == 0) {
            onlyOne ^= cur;
        }
    }
    retArr[0] = onlyOne;
    retArr[1] = onlyOne ^ eor;
    return retArr;
}

leecode类似题目

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只
出现一次的数字。 
数据范围：数组长度 ，数组中每个数的大小 要求：空间复杂度 ，时间复杂度 提示：输出时按非降序排列。
提示：输出时按非降序排列。

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        // write code here
        if (nums == null || nums.length < 2){
            return null;
        }
        int eor = 0;
        for (int i = 0;i < nums.length;++i){
            eor ^= nums[i];
        }
        int rightNumber = eor & (~eor + 1);
        int onlyOne = 0;
        for(int i= 0;i < nums.length;++i){
            if((nums[i] & rightNumber) == 0){
                onlyOne ^= nums[i];
            }
        }
        int otherOne = (eor ^ onlyOne);
        int maxValue = onlyOne > otherOne ? onlyOne : otherOne; 
        int minValue = onlyOne > otherOne ? otherOne : onlyOne; 
        return new int[]{minValue,maxValue};
    }
}

二进制相关的其他算法

 
获取一个整数中二进制数1的个数

 /**
  * 获取二进制数中1的个数
  * @param n
  * @return
  */
 public static int getCount(int n) {
     int iCount = 0;
     while (n != 0) {
         // 一个数n按位与(n-1)则会删除最右侧的1
         n = n & (n - 1);
         iCount++;
     }
     return iCount;
 }


/**
  * 获取二进制数中1的个数
  * @param n
  * @return
  */
 public static int getCount(long n) {
     long one = 1;
     int iCount = 0;
     for (int i = 0; i < 63 ; i++) {
         if ((n & one << i) != 0){
             iCount ++;
         }
     }
     return iCount;
 }

4 插入排序时间复杂度分析 ( O ( n 2 ) ) (O(n^2)) (O(n2))

coding
插入排序在某些数据状况下,时间复杂度比选择排序和冒泡排序要好

从0开始 依次保证从 0 - (N -1)范围上有序

public class InsertSortTest {
    public static void  insertSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        // 0 - 0有序
        // 0 - i有序
        for (int i = 1; i < arr.length ; i++) {
        	// j 位置的数 比 j + 1 位置上的数大 就交换
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr,j,j + 1);
            }
        }
    }

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

C++ 版本实现

template <typename T>
static void swap(int32 i, int32 j, T arr[])
{
   arr[i] = arr[i] ^ arr[j];
   arr[j] = arr[i] ^ arr[j];
   arr[i] = arr[i] ^ arr[j];
}

template <typename T, int32 N>
static void insertSort(T arr[])
{
    if (arr == NULL || N < 2)
    {
        return;
    }
    for (int32 i = 1; i < N; ++i)
    {
        for (int32 j = i; j > 0 && arr[j - 1] > arr[j]; --j)
        {
            swap<T>(j, j - 1, arr);
        }
    }
}

// C++ 模板中的非类型参数
template <typename T, int32 N>
static void printArr(T arr[])
{
    for (int32 index = 0; index < N; ++index)
    {
        cout << arr[index] << " ";
    }
    cout << endl;
}

void test_insertSort()
{
   int32 arr[] = {90,20,13,78,60,56};
   const int32 arrSize = sizeof(arr) / sizeof(int32);
   insertSort<int32,arrSize>(arr);
   printArr<int32,arrSize>(arr);
}

5 二分法的详解与扩展

1 在一个有序数组中找某个数是否存在

public class BinarySearchTest {
    public static void main(String[] args) {
        int[] arr = {9,12,14,17,28,35,49};
        System.out.println(isExists(arr,14));
    }
    // 二分查找
    public static boolean isExists(int[] arr,int num){
        if (arr == null || arr.length == 0){
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        // 第一个位置和最后一个位置就是  直接返回
        if (arr[L] == num || arr[R] == num){
            return true;
        }
        // 不是 才开始二分查找
        while ( L < R) {
           int mid = L + ((R -L) >> 1);
           if (arr[mid] < num){
                // 往右半查找
               L = mid + 1;
           } else if (arr[mid] > num){
               //往左半查找
               R = mid - 1;
           } else {
               return true;
           }
        }
        return arr[L] == num;
    }
}

2 在一个数组中,找一个数最左侧的位置 同样可以使用二分法查找

/**
     *  在一个有序数组中，找>=某个数最左侧的位置
     * @param arr
     * @param X
     * @return
     */
    public static int searchLeftValue(int[] arr,int X){
        if (arr == null || arr.length == 0){
            return -1;
        }
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while ( L < R){
            int mid = L + ((R - L) >> 1);
            if (arr[mid] < X) { // 小于的时候就是往右找
                L = mid + 1;
            } else if (arr[mid] >= X){ // 打到中间位置  往左找
               index = mid;
               R = mid - 1;
            }
        }
        return index;
    }

leetcode题目

请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if(nums == null || nums.length == 0){
            return -1;
        }

        if(nums[0] == target){
            return 0;
        }

        if(nums[nums.length - 1] == target){
            return nums.length - 1;
        }
        int index = -1;
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while(leftIndex < rightIndex){
            int mid = leftIndex + ((rightIndex - leftIndex) >> 1);
            if(nums[mid] < target){
                leftIndex = mid + 1;
            } else if (nums[mid] > target) {
                rightIndex = mid - 1;
            } else {
                return mid; 
            }
        }
        if(nums[leftIndex] == target){
            index = leftIndex;
        }
        return index;
    }
}

3 在一个有序数组中,找$\le$ 某个数最右侧的位置
coding

/**
  * 在一个有序数组中,找<= 某个数最右侧的位置
  * @param arr
  * @param X
  * @return
  */
 public static int getRightValue(int[] arr,int X){
     if (arr == null || arr.length == 0){
         return -1;
     }
     int L = 0;
     int R = arr.length - 1;
     int index = -1;
     while (L < R) {
         int M = L + ((R - L) >> 1);
         // 中间位置的数小于等于X 往右继续找
         if (arr[M] <= X) {
             index = M;
             L = M + 1;
         } else{
           R = M - 1;
         }
     }
     return index;
 }

4 局部最小问题 (数组无序,相邻的两个数一定不相等)
coding

/**
     *  局部最小值问题：
     * 无序数组，任意两个相邻的数不等，找到存在局部最小的位置
     * 0位置比1位置小，则0位置是局部最小，n-2位置比n-1位置小，返回n-1位置
     * 中间位置i，需满足 i 比左边小也比右边小，则i位置是局部最小
     * 局部最小位置存在即可返回，不用返回所有的位置
     * @param arr
     * @return
     */
    public static int getLessIndex(int[] arr){
        if (arr == null || arr.length == 0){
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]){
            return 0;
        }
        if (arr[arr.length -1 ] < arr[arr.length -2 ]){
            return arr.length -1 ;
        }
        int L = 1;
        int R = arr.length - 2;
        while (L < R){
            int M = L + ((R - L) >> 1);
            // 中点位置的数比后一个数要大 往右查找
            if (arr[M] > arr[M+1]){
                L = M + 1;
            } else if (arr[M] > arr[M-1]){ // 中点位置的数比前一个数要大 往左查找
                R = M -1;
            } else { // 中点位置的数小于前一个 也小于后一个 直接返回
                return M;
            }
        }
        return L;
    }

leetcode 类似题目

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，
在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？

coding

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 此问题实际上是局部最大问题
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        if(nums == null || nums.length == 0){
            return -1;
        }
        if(nums.length == 1 || nums[0] > nums[1]){
            return 0;
        }
        if(nums[nums.length - 1] > nums[nums.length - 2]){
            return nums.length -1;
        }
        int L = 1;
        int R = nums.length - 2;
        while(L < R){
            int M = L + ((R - L) >> 1);
            // 当前数比后一个要小 往右半查找
            if(nums[M] < nums[M + 1]){
                L = M + 1;
             // 中间的数比前一个数大 则往左半查找   
            } else if (nums[M] < nums[M - 1] ){
                R = M - 1;
             // 中间的数比后一个大且比前一个大 则当前数就是最大的
            } else {
                return M;
            }
        }
        return L;
    }
}

6 对数器

对数器的概念和使用

1. 有一个你想要测试的方法A
2. 实现复杂度不好但是容易实现的方法
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本
5. 如果有一个随机样本使得比对结果不一致,打印样本进行人工干预,改对方法A或者方法B
6. 当样本量很多时比对测试依然正确,可以确定方法A已经正确

coding

public static void test1() {
  int testTime = 5000000;
  boolean isSucceed = true;
  long startTime = System.currentTimeMillis();
  for (int i = 0; i < testTime; ++i) {
      int[] arr = genRandArr(100, 100);
      int[] cpyArr = copyArray(arr);
      Arrays.sort(cpyArr);
      selectSort(arr);
      if (!isEqual(arr, cpyArr)) {
          isSucceed = false;
          break;
      }
  }
  long endTimes = System.currentTimeMillis();
  System.out.println((endTimes - startTime));
  System.out.println(isSucceed ? "success" : "failed");
}


// 生成随机数
// Math.random() 返回 [0-1)之间的小数
public static int[] genRandArr(int maxSize, int maxValue) {
	// 0 <= Math.random() < 1.0 
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; ++i) {
        arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
    }
    return arr;
}

public static int[] copyArray(int[] srcArr) {
    int[] destArr = new int[srcArr.length];
    System.arraycopy(srcArr, 0, destArr, 0, srcArr.length);
    return destArr;
}

public static boolean isEqual(int[] arr1, int[] arr2) {
    if (arr1.length != arr2.length) return false;
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) return false;
    }
    return true;
}


/**
 * 选择排序
 *      每次选择出最小的数放在指定的位置
 * @param arr
 */
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                swap(arr, i, j);
            }
        }
    }
}

7 归并排序

整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
让其整体有序的过程里用了外排序方法

public static void mergeSort(int arr[]){
         if (arr == null || arr.length < 2){
             return;
         }
         processSort(arr,0,arr.length-1);
 }

 public static void  processSort(int[] arr,int L,int R){
        if (R == L){
            return;
        }
        int M = L + ((R-L) >> 1);
        // 先让左边有序
        processSort(arr,L,M);
        // 再让右边有序
        processSort(arr,M+1,R);
        // 最后合并
        merge(arr,L,M,R);
 }

 // 将左边和右边合并 合并过程的时间复杂度是O(N)
 public static void merge(int[] arr,int L,int M,int R){
     // 创建一个数组 拷贝数据
     int[] tempArr = new int[R - L + 1];
     // 临时数组索引
     int index = 0;
     // 指向左边数组的下标
     int p1 = L;
     // 指向右边有序数组的下标
     int p2 = M+1;
     // 两边都不越界
     while(p1 <= M && p2 <= R) {
         tempArr[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
     }

     // 左边不越界
     while(p1 <= M){
         tempArr[index++] = arr[p1++];
     }

     // 右边不越界
     while (p2 <= R){
         tempArr[index++] = arr[p2++];
     }
	 // 将排好序的数据拷贝到原数组中		
     for (int i = 0;i<tempArr.length;++i){
         arr[L+i] = tempArr[i];
     }
 }

8 归并排序的应用

求小和问题
小和问题和逆序对问题
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
的小和。求一个数组 的小和。
例子:[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

小和问题可以转换成右侧有几个数比它大
时间复杂度为 O(N^2)

 // 时间复杂度 O(N^2)
    public static int vioMethod(int[] arr){
        int ret = 0;
        for (int i = 1;i < arr.length;++i){
            for(int j = 0;j < i;++j){
                if (arr[j] < arr[i]){
                    ret+=arr[j];
                }
            }
        }
        return  ret;
    }

使用归并排序改写

// 既要排好序  又要求小和
public static int smallSum(int[] arr){
   if (arr == null || arr.length < 2) {
       return 0;
   }
   return process(arr,0,arr.length-1);
}

public static int process(int[] arr,int L,int R){
   if (L == R){
       return 0;
   }
   int mid = L + ((R-L) >>1);
   // 返回左边合并之前的小和 + 右边合并之前的小和 + 两边合并之后的小和
   return process(arr,L,mid) + process(arr,mid + 1,R) + smallMerge(arr,L,mid,R);
}

public static int smallMerge(int[] arr,int L,int M,int R){
   int[] tempArr = new int[R - L + 1];
   int index = 0;
   int p1 = L;
   int p2 = M + 1;
   int ret = 0;

   while(p1 <= M && p2 <= R){
   	   // 相等的时候 右组先拷贝 并且不产生小和 
       ret += arr[p1] < arr[p2] ? (R - p2 +1) * arr[p1] : 0;
       // 谁小拷贝谁
       tempArr[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
   }

   while (p1 <= M){
       tempArr[index++] = arr[p1++];
   }
   while (p2 <= R){
       tempArr[index++] = arr[p2++];
   }
   for(int i = 0;i < tempArr.length;++i){
       arr[L + i]  = tempArr[i];
   }
   return  ret;
}

9 逆序对问题

逆序对问题 在一个数组中，左边的数如果比右边的数大，则这两个数
构成一个逆序对，请打印所有逆序对,求出逆序对的个数

    public static class InversePair {
        private int maxVal;
        private int minVal;

        public InversePair () {}

        public InversePair(int maxVal, int minVal) {
            this.maxVal = maxVal;
            this.minVal = minVal;
        }

        public int getMaxVal() {
            return maxVal;
        }

        public void setMaxVal(int maxVal) {
            this.maxVal = maxVal;
        }

        public int getMinVal() {
            return minVal;
        }

        public void setMinVal(int minVal) {
            this.minVal = minVal;
        }

        @Override
        public String toString() {
            return "InversePair{" +
                    "maxVal=" + maxVal +
                    ", minVal=" + minVal +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            InversePair that = (InversePair) o;
            return maxVal == that.maxVal &&
                    minVal == that.minVal;
        }

        @Override
        public int hashCode() {
            return Objects.hash(maxVal, minVal);
        }
    }

    private static List<InversePair> inversePairs = new ArrayList<>();

    public static void main(String[] args) {
        int[] arr = {8,7,6,5,4,3,2,1};
        System.out.println(getReverseOrderCnt(arr));
        for (InversePair pair : inversePairs) {
            System.out.println(pair);
        }
    }

    public static int getReverseOrderCnt(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        return process(arr,0,arr.length - 1);
    }

    public static int process(int[] arr,int L,int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R -L) >> 1);
        return process(arr,L,M) + process(arr,M+1,R) + merge(arr,L,M,R);
    }

    public static int merge(int[] arr,int L,int M,int R){
        int[] tempArr = new int[R - L + 1];
        int p1 = L;
        int p2 = M + 1;
        int index = 0;
        int ret = 0;
        // 这里一定是有一边是拷贝完成的
        while (p1 <= M && p2 <= R){
            // 升序排列  谁大拷贝谁
            ret += arr[p1] > arr[p2] ? (R - p2 + 1) : 0;
            if (arr[p1] > arr[p2]){
                int tempIndex = p2;
                while (tempIndex <= R){
                   inversePairs.add(new InversePair(arr[p1],arr[tempIndex++]));
                }
            }
            tempArr[index++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= M) {
            tempArr[index++] = arr[p1++];
        }

        while (p2 <= R){
            tempArr[index ++] = arr[p2++];
        }

        for (int i = 0; i < tempArr.length ; i++) {
            arr[L + i] = tempArr[i];
        }
        return ret;
    }

leetcode 题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
即输出$Pmod1000000007$
要求：空间复杂度$O(n)$，时间复杂度$O(nlogn)$

数据范围： 对于

import java.util.*;


public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param nums int整型一维数组
   * @return int整型
   */
  public int InversePairs (int[] nums) {
    // write code here
    if (nums == null || nums.length < 2) {
      return 0;
    }
    int count = process(nums, 0, nums.length - 1);
    return (count % 1000000007);
  }

  public int process(int[] nums, int L, int R) {
    if (L == R) {
      return 0;
    }
    int M = L + ((R - L) >> 1);
    // 左侧递归产生的逆序对个数 + 右侧递归产生的逆序对个数 + 合并之后产生的逆序对个数
    return process(nums, L, M) + process(nums, M + 1, R) + merge(nums, L, M, R);
  }

  public int merge(int[] nums, int L, int M, int R) {
    int[] tempArr = new int[R - L + 1];
    int p1 = L;
    int p2 = M + 1;
    // 辅助数组的索引下标
    int index = 0;
    int count = 0;
    // 合并的左边和右边都不越界
    while (p1 <= M && p2 <= R) {
      // 小于等于的时候 左边的数字不会产生逆序对 直接进行拷贝
      if(nums[p1] <= nums[p2]){
          tempArr[index ++] = nums[p1++];
      } else {
          count += (M - p1 + 1);
          count %= 1000000007;
          tempArr[index++] = nums[p2++];
      }
    }
    // 数据大的一边一定是拷贝完成的 因此不会产生逆序对
    while (p1 <= M) {
      tempArr[index++] = nums[p1++];
    }
    while (p2 <= R) {
      tempArr[index++] = nums[p2++];
    }
    for (int i = 0; i < tempArr.length; i++) {
      nums[L + i] = tempArr[i];
    }
    return count;
  }
}

10 归并排序非递归方式

public class MergeSortNoRecursionTest {

    public static void main(String[] args) {
        int[] arr = {10,7,6,2,10,3,90,23,12};
        mergeSortNoRecursion(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSortNoRecursion(int arr[]){
        if (arr == null || arr.length < 2){
            return;
        }
        int N = arr.length;
        // 步长
        int mergeSize = 1;
        while (mergeSize < N){
            // 当前左组的第一个位置
            int L = 0;
            // 左组的位置不能越界
            while (L < N){
                // 中间位置
                int M = L + mergeSize - 1;
                // 不够退出
                if (M >= N){
                    break;
                }
                // 右组的位置如果够 会来到 M + mergeSize  越界右组的位置就是 N -1
                int R = Math.min(M + mergeSize,N - 1 );
                merge(arr,L,M,R);
                // 左组的位置取到上一次右组位置的下一个位置
                L = R + 1;
            }
            // 防止溢出
            if (mergeSize > N /2){
                break;
            }
            // 步长乘2
            mergeSize <<= 1;
        }
    }

    public static void merge(int[] arr,int L,int M,int R){
        int[] tempArr = new int[R - L + 1];

        int index = 0;
        int p1 = L;
        int p2 = M + 1;

        while (p1 <= M && p2 <= R){
            tempArr[index++] = arr[p1] <= arr[p2] ? arr[p1 ++] : arr[p2 ++];
        }

        while (p1 <= M){
            tempArr[index ++] = arr[p1 ++];
        }

        while (p2 <= R){
            tempArr[index ++] = arr[p2 ++];
        }

        for (int  i = 0 ; i < tempArr.length;i++){
            arr[L + i] = tempArr[i];
        }
    }
}

 
头文件声明
 

C++版本 冒泡排序 插入排序 选择排序 归并排序

#ifdef _WIN64
#include "common\common_def.h"
#elif __linux__
#include "common/common_def.h"
#else
#include "common\common_def.h"
#endif
#include <algorithm>
#include <iostream>

#ifndef __SORT_H__
#define __SORT_H__
namespace SORT_TEST
{
    static void swap(int32 arr[], int32 i, int32 j)
    {
        int32 temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void swap_bit(int32 arr[], int32 i, int32 j)
    {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j]; // arr[i] ^ arr[j] ^ arr[j] = arr[i] ^ 0 = arr[i]
        arr[i] = arr[i] ^ arr[j]; // arr[i] ^ arr[i] ^ arr[j] = 0 ^ ^ arr[j] = arr[j]
    }

    static void printArr(int32 arr[], int len)
    {
        FUNCTION_BGEIN
        for (int32 idx = 0; idx < len; ++idx)
        {
            std::cout << arr[idx] << " ";
        }
        std::cout << "\n";
        FUNCTION_END
    }
    /**
     * @brief 使用递归的方式获取到数组中的最大值
     *
     * @param arr
     * @param len
     * @return int32
     */
    int32 max(int32 arr[], int32 len);

    int32 processMax(int32 arr[], const int32 &iLeftIndex, const int32 &iRightIndex);
    /**
     * @brief 选择排序
     *
     * @param arr
     * @param len
     */
    void selectSort(int32 arr[], int32 len);

    /**
     * @brief 冒泡排序
     *
     * @param arr
     * @param len
     */
    void bubbleSort(int32 arr[], int32 len);

    /**
     * 插入排序算法 包括 :
     *  直接插入排序算法   折半插入排序 2路插入排序 表插入排序  希尔排序
     * @brief 插入排序
     *
     * @param arr
     * @param len
     */
    void insertSort(int32 arr[], int32 len);

    /**
     * @brief  直接插入排序 算法的时间复杂度 O(n^2)
     *
     * @param arr
     * @param len
     */
    void inserSortDirect(int32 arr[], int32 len);

    /**
     * @brief  折半插入排序 查找插入位置时  使用二分查找
     *
     * @param arr
     * @param len
     */
    void insertSortHalf(int32 arr[], int32 len);

    /**
     * @brief 二路插入排序算法
     *
     * @param arr
     * @param len
     */
    void inserSort2(int32 arr[], int32 len);

    /**
     * @brief 归并排序
     *
     * @param arr
     * @param len
     */
    void mergeSort(int32 arr[], int32 len);

    /**
     * @brief 处理归并排序 递归方式
     *
     * @param arr
     * @param L
     * @param R
     */
    void processMergeSort(int32 arr[], int32 L, int32 R);

    /**
     * @brief  数组按顺序合并
     *
     * @param arr
     * @param M
     * @param L
     * @param R
     */
    void merge(int32 arr[], int32 M, int32 L, int32 R);

    /**
     * @brief 归并排序 非递归方式
     *
     * @param arr
     * @param len
     */
    void mergeSortNoRecur(int32 arr[], int32 len);

    /**
     * @brief 把小于pivot的数放在数组的左边 大于pivot的数放在数组的右边
     *
     * @param arr
     * @param L
     * @param R
     * @param pivot
     */
    void partition(int32 arr[], const int32 &L, const int32 &R, const int32 &pivot);

    /**
     * @brief
     * 把小于pivot的数放在数组的左边 等于pivot的数放在数组的中间 大于pivot的数放在数组的右边
     *
     * @param arr
     * @param L
     * @param R
     * @param pivot
     */
    void patition_equal(int32 arr[], const int32 &L, const int32 &R, const int32 &pivot);
}
#endif // __SORT_H__

源文件

#include "sort.h"
namespace SORT_TEST
{
    int32
    max(int32 arr[], int32 len)
    {
        return processMax(arr, 0, len);
    }

    int32 processMax(int32 arr[], const int32 &iLeftIndex, const int32 &iRightIndex)
    {
        if (iLeftIndex == iRightIndex)
        {
            return arr[iLeftIndex];
        }

        int32 midIndex = iLeftIndex + ((iRightIndex - iLeftIndex) >> 1);
        // 求左边的最大值
        int32 iLeftMax = processMax(arr, iLeftIndex, midIndex);
        // 求右边最大值
        int32 iRightMax = processMax(arr, midIndex + 1, iRightIndex);

        return std::max(iLeftMax, iRightMax);
    }

    void selectSort(int arr[], int len)
    {
        FUNCTION_BGEIN
        if (len < 2)
        {
            return;
        }
        for (int32 i = 0; i < len - 1; ++i)
        {
            int32 minIndex = i;
            for (int32 j = i + 1; j < len; ++j)
            {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
        FUNCTION_END
    }

    void bubbleSort(int32 arr[], int32 len)
    {
        if (len < 2)
        {
            return;
        }
        // 外层循环控制冒泡范围
        for (int32 i = len - 1; i > 0; --i)
        {
            // 内层循环找到冒泡范围上的最大值
            for (int32 j = 0; j < i; ++j)
            {
                if (arr[j] > arr[j + 1])
                {
                    swap_bit(arr, j, j + 1);
                }
            }
        }
    }

    void insertSort(int32 arr[], int32 len)
    {
        FUNCTION_BGEIN
        if (len < 2)
        {
            return;
        }
        // i 要往前插入的数据的索引
        for (int32 i = 1; i < len; ++i)
        {
            // j 表示 i位置上的数应该在的位置
            for (int32 j = i; j > 0 && arr[j] < arr[j - 1]; --j)
            {
                swap_bit(arr, j, j - 1);
            }
        }
        FUNCTION_END
    }

    void inserSortDirect(int32 arr[], int32 len)
    {
        FUNCTION_BGEIN
        if (len < 2)
        {
            return;
        }
        for (int idx = 1; idx < len; ++idx)
        {
            int32 insertPos = idx;
            int32 temp = arr[idx];

            // 查找插入的位置  只要发现当前这个数比查找位置的数小往前走
            while (insertPos > 0 && temp < arr[insertPos - 1])
            {
                arr[insertPos] = arr[insertPos - 1];
                --insertPos;
            }
            // 找到了插入的位置
            arr[insertPos] = temp;
        }
        FUNCTION_END
    }

    void insertSortHalf(int32 arr[], int32 len)
    {
        FUNCTION_BGEIN
        if (len < 2)
        {
            return;
        }
        for (int32 i = 1; i < len; ++i)
        {
            int32 insertPos = i;
            int32 temp = arr[i];
            // 查找插入位置 使用二分查找 查找最右边小于等于的数
            int32 L = 0;
            int32 R = i - 1;
            while (L < R)
            {
                int32 mid = L + ((R - L) >> 1);
                // 当前这个值不小于中间位置的值 往右边去找
                if (arr[mid] <= temp)
                {
                    L = mid + 1;
                }
                else // 当前这个值比中间位置要小  则往左边找
                {
                    R = mid - 1;
                }
            }
            // 找到要插入的位置是 L + 1
            LOG_TRACE("find index : %d\n", L + 1);

            // 把 L + 1 到 i -1 位置的数往后挪
            for (int j = i; j > L + 1; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[L + 1] = temp;
        }
        FUNCTION_END
    }

    void inserSort2(int32 arr[], int32 len)
    {
        FUNCTION_BGEIN
        if (len < 2)
        {
            return;
        }
        int *pHelpArr = new int32[len];

        int32 minIndex = 0; // 临时数组中最小值的索引
        int32 maxIndex = 0; // 临时数组中最大最的索引

        pHelpArr[0] = arr[0];

        for (int32 idx = 1; idx < len; ++idx)
        {
            if (arr[idx] < arr[minIndex]) // 小于临时数组中的最小值
            {
                minIndex = (minIndex - 1 + len) % len; // 新的最小值的索引
                pHelpArr[minIndex] = arr[idx];
            }
            else if (arr[idx] > arr[maxIndex]) // 大于临时数组中的最大值
            {
                maxIndex = (maxIndex + 1 + len) % len;
                pHelpArr[maxIndex] = arr[idx];
            }
            else
            {
                int32 insertIndex = (maxIndex + 1 + len) % len;
                while (pHelpArr[(insertIndex - 1 + len) % len] > arr[idx])
                {
                    pHelpArr[(insertIndex + len) % len] = pHelpArr[(insertIndex - 1 + len)];
                    insertIndex = (insertIndex - 1 + len) % len;
                }
                pHelpArr[(insertIndex + len) % len] = arr[idx];
                maxIndex = (maxIndex + 1 + len) % len;
            }
        }

        for (int32 idx = 0; idx < len; ++idx)
        {
            arr[idx] = pHelpArr[(idx + len) % len];
        }

        delete[] pHelpArr;
        FUNCTION_END
    }

    void mergeSort(int32 arr[], int32 len)
    {
        if (len < 2)
            return;
        processMergeSort(arr, 0, len - 1);
    }

    void processMergeSort(int32 arr[], int32 L, int32 R)
    {
        // FUNCTION_BGEIN
        if (L == R)
        {
            return;
        }
        int32 M = L + ((R - L) >> 1);
        // LOG_TRACE("L : %d,M : %d,R : %d\n", L, M, R);
        processMergeSort(arr, L, M);
        // LOG_TRACE("L : %d,M + 1: %d,R : %d\n", L, M + 1, R);
        processMergeSort(arr, M + 1, R);
        merge(arr, M, L, R);
        // FUNCTION_END
    }

    void merge(int32 arr[], int32 M, int32 L, int32 R)
    {
        FUNCTION_BGEIN
        LOG_TRACE("L : %d,R : %d\n", L, R);
        const int32 arrLen = (R - L + 1);
        int32 *tempArr = new int32[arrLen];
        int32 index = 0; // 临时数组下标
        int32 p1 = L;
        int32 p2 = M + 1;

        // 两边都不越界
        while (p1 <= M && p2 <= R)
        {
            tempArr[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= M)
        {
            tempArr[index++] = arr[p1++];
        }

        while (p2 <= R)
        {
            tempArr[index++] = arr[p2++];
        }

        for (int32 i = 0; i < arrLen; ++i)
        {
            arr[L + i] = tempArr[i];
        }

        delete[] tempArr;
        FUNCTION_END
    }

    void mergeSortNoRecur(int32 arr[], int32 len)
    {
        FUNCTION_BGEIN
        if (len < 2)
            return;

        int32 stepSize = 1; // 步长  被合并数组一半的长度
        for (; stepSize < len; stepSize = stepSize << 1)
        {
            // 每次步长开始时的位置
            int32 L = 0;
            while (L < len)
            {
                int32 M = L + stepSize - 1;
                // 左组已经不够 则直接退出
                if (M >= len)
                {
                    break;
                }
                int32 R = std::min(M + stepSize, len - 1);
                // LOG_TRACE("L : %d,R : %d\n", L, R);
                merge(arr, M, L, R);
                L = R + 1;
            }
            if (stepSize > (len >> 1))
                break;
        }
        FUNCTION_END
    }

    void partition(int32 arr[], const int32 &L, const int32 &R, const int32 &pivot)
    {
        FUNCTION_BGEIN
        int32 less = L - 1; // 小于区域右边界
        int32 more = R;     // 大于区域左边界
        int32 idx = L;      // 数组的索引
        while (idx < more)
        {
            if (arr[idx] <= pivot) // 当前数小于指定的数 则和小于区域的下一个做交换
            {
                LOG_TRACE("arr[idx] : %d\n", arr[idx]);
                swap(arr, idx++, ++less);
            }
            else
            {
                LOG_TRACE("arr[idx] : %d\n", arr[idx]);
                swap(arr, idx, --more); // 和大于区域的前一个做交换
            }
        }
        FUNCTION_END
    }

    void patition_equal(int32 arr[], const int32 &L, const int32 &R, const int32 &pivot)
    {
        FUNCTION_BGEIN
        int32 less = L - 1;
        int32 more = R;
        int32 idx = L;

        while (idx < more)
        {
            if (arr[idx] < pivot) // 小于给定的值  则与小于区域右边界的下一个做交换
            {
                swap(arr, idx++, ++less);
            }
            else if (arr[idx] == pivot) // 直接下一个
            {
                ++idx;
            }
            else // 大于 和大于区域右边界的前一个做交换
            {
                swap(arr, idx, --more);
            }
        }
        FUNCTION_END
    }
}

11 快速排序

首先来看如下问题
荷兰国旗问题
问题1 : 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

解决步骤 :
划分小于的区域 一开始在最左边
遍历数组,如果当前值不超过num,则和小于等于区域的下一个数作交换,小于等于区域往右扩,如果当前数大于num,则直接遍历下一个,直到遍历完成结束
小于等于区域一直在推着等于区域往右走

package com.chao.test;

import java.util.Arrays;

/**
 * @author Mrchao
 * @version 1.0.0
 * @date 2023-07-22
 */
public class NetherlandsFlagTest {
    public static void main(String[] args) {
        int[] arr = {9,5,10,4,4,6,7,7,8,10,7,10};
        partition(arr,0,arr.length - 1,7);
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    /**
     * 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，
     * 等于num的数放在数组的中间，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)
     * @param arr
     * @param l 数组的左边界
     * @param r 数组的右边界
     * @param p 比较的数
     */
    public static void partition(int[] arr,int l,int r,int p) {
        // 小于区域的左边界
        int less = l - 1;
        // 大于区域右边界
        int more = r + 1;
        while (l < more){
            // 当前数小于给定的数 当前数和小于区域的下一个做交换 l继续往后走
            if (arr[l] <= p){
                swap(arr,l++,++less);
            } else { // 当前数大于给定的数 和大于区域的前一个数做交换 l不动
                swap(arr,l,--more);
            }
        }
    }
}

问题 2
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

处理步骤 :
划分小于区域的右边界 划分大于区域的左边界
遍历数组

1. arr[i] < num [i]和 小于区域的下一个作交换, 小于区域往右扩,i++
2. arr[i] == num 继续遍历 i ++
3. arr[i] > num arr[i]和大于区域的前一个作交换 ,大于区域左扩,i原地不动

import java.util.Arrays;

/**
 * @author Mrchao
 * @version 1.0.0
 * @date 2023-07-22
 */
public class NetherlandsFlagTest {
    public static void main(String[] args) {
        int[] arr = {9,5,10,4,4,6,7,7,8,10,7,10};
        partition(arr,0,arr.length - 1,7);
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    /**
     * 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，
     * 等于num的数放在数组的中间，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)
     * @param arr
     * @param l 数组的左边界
     * @param r 数组的右边界
     * @param p 比较的数
     */
    public static void partition(int[] arr,int l,int r,int p) {
        // 小于区域的左边界
        int less = l - 1;
        // 大于区域右边界
        int more = r + 1;
        while (l < more){
            // 当前数小于给定的数 当前数和小于区域的下一个做交换 l继续往后走
            if (arr[l] < p){
                swap(arr,l++,++less);
            //当前数大于给定的数 和大于区域的前一个数做交换 l不动
            } else if (arr[l] > p){ 
                swap(arr,l,--more);
            } else { // 直接下一个
                l ++;
            }
        }
    }
}

快排第一个版本
选数组中的最后一个数作划分值,将小于等于此划分值的数都放在数组的左边,然后将划分值和数组小于区域的下一个值做交换,则此划分值左边都是小于等于此划分值的,此值右侧都是大于此划分值的,然后让左侧和右侧递归重复此过程,最终会让整个数组都有序

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

    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        process(arr,0,arr.length - 1);
    }

    public static void  process(int[] arr,int L,int R){
        if (L >= R) {
            return;
        }
        int lessIndex = partition(arr, L, R);
        process(arr,L,lessIndex);
        process(arr,lessIndex + 2,R);
    }

    public static int partition(int[] arr,int L,int R){
        int pivot = arr[R];
        int less = L - 1;
        int more = R;
        while (L < more){
        	// 当前值比最右边的值小于或等于 当前值和小于区域的下一个值做交换
            if (arr[L] <= pivot){
                swap(arr,++less,L++);
            } else {
                swap(arr,L,--more);
            }
        }
        swap(arr,less + 1,R);
        // 返回小于区域的右边界
        return less;
    }

快排第二个版本

就是荷兰国旗问题
一开始选数组整个范围上的最后一个值作为划分值,划分出小于这个划分值的区域,等于这个划分值的区域,大于这个划分值的区域,然后将这个划分值和大于区域的第一个值做交换,则在排序过程中,此划分值在数组中的位置就不会动了

不改进的排序 :
1）划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低
2）可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)

快速排序第三版本
如果划分值打在了中间,则满足master公式 T(N) = 2 * T(N/2) + O(N)

在数组的范围上[L,R],随机选择一个数作为划分值,好的情况和差的情况是等概率事件,把所有情况累加,再求数学上的长期期望,最后得到时间复杂度是 O(N*logN)
快排的额外空间复杂度O(logN)

coding

 /**
  * i != j
  *
  * @param arr
  * @param i
  * @param j
  */
 public static void swap(int[] arr, int i, int j) {
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
 }

 public static void quickSort(int[] arr) {
     if (arr == null || arr.length < 2) {
         return;
     }
     quickSort(arr,0,arr.length -1);
 }

 public static void quickSort(int[] arr, int L, int R) {
     if (L < R) {
         // 随机选一个数 和最右边的数做交换
         swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
         int[] p = partition(arr,L,R);
         // p[0] 等于区域的左边界
         quickSort(arr,L,p[0] - 1); // 小于区域右边界
         // p[1] 等于区域的右边界
         quickSort(arr,p[1] + 1,R);// 大于区域左边界
     }
 }
 /**
  *
  * @param arr
  * @param L 分区的左边界
  * @param R 分区的右边界
  * @return  划分值等于区域的左边界和右边界
  */
 public static int[] partition(int[] arr, int L, int R) {
     // 小于区域的左边界
     int less = L - 1;
     // 大于区域的右边界
     int more = R; 
     while (L < more) { // L往右边走  more 往左边走
         // arr[R] 当前的划分值
         // 当前数小于划分值,当前值和小于区域的下一个值做交换
         if (arr[L] < arr[R]) { 
             swap(arr, ++less, L++);
          //当前数大于划分值 和大于区域的前一个值做交换   
         } else if (arr[L] > arr[R]) {
             swap(arr, --more, L);
         } else { // 等于的时候 直接往下走
             L++;
         }
     }
     // 大于区域的第一个数和最后一个数做交换
     swap(arr, more, R);
     // [等于区域的左边界,等于区域的右边界]
     return new int[]{less + 1, more};
 }

import java.util.Arrays;
import java.util.Stack;

/**
 * @author Mrchao
 * @version 1.0.0
 * @date 2023-07-23
 */
public class QuickSortNonRecurTest {
    public static void main(String[] args) {
        int[] arr = {5,2,6,7,10,21};
        quickSortNonRecur(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void  quickSortNonRecur(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        process(arr,0,arr.length - 1);
    }

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

    public static void process(int[] arr,int leftBorder,int rightBorder){
        Stack<Integer> indexStack = new Stack<>();
        indexStack.push(rightBorder);
        indexStack.push(leftBorder);
        while (!indexStack.isEmpty()){
            int leftIndex = indexStack.pop();
            int rightIndex = indexStack.pop();
            int selectIndex = leftIndex + (int) Math.random() * (rightIndex - leftIndex + 1);
            swap(arr,selectIndex,rightBorder);
            int[] par = partition(arr, leftIndex, rightIndex);
            // 大于区域进栈
            if (par[1] + 1 < rightIndex){
                indexStack.push(rightIndex);
                indexStack.push(par[1] + 1);
            }
            // 小于区域进栈
            if (par[0] - 1 > leftIndex){
                indexStack.push(par[0] - 1);
                indexStack.push(leftIndex);
            }
        }

    }

    public static int[] partition(int[] arr,int leftIndex,int rightIndex){
        int less = leftIndex - 1;
        int more = rightIndex;
        while (leftIndex < more){
            if (arr[leftIndex] < arr[rightIndex]){
                swap(arr,++less,leftIndex++);
            }else if (arr[leftIndex] > arr[rightIndex]){
                swap(arr,--more,leftIndex);
            }else {
                ++ leftIndex;
            }
        }
        swap(arr,rightIndex,more);
        return new int[] {less + 1,more};
    }
}

C++版本

头文件声明

#ifdef _WIN64
#include "common\common_def.h"
#elif __linux__
#include "common/common_def.h"
#else
#include "common/common_def.h"
#endif

#ifndef __QUICK_SORT_H__
#define __QUICK_SORT_H__
/**
 * @brief 快速排序第一个版本 把最右侧的数作为划分值 
 * 
 * 
 * @param arr 
 * @param R 
 */
void quickSortV1(int32 arr[],int32 R);

int32 partitionV1(int32 arr[], int32 L, int32 R);

void processQuickSortV1(int32 arr[], int32 L, int32 R);

/**
 * @brief 快速排序第2个版本 一次搞定多个数
 * 
 * 
 * @param arrp 
 * @param R 
 */
void quickSortV2(int32 arrp[], int32 R);

void processQuickSortV2(int32 arr[], int32 L, int32 R);

void partitionV2(int32 arr[], int32 L, int32 R,std::vector<int32>& vecIdx);

#endif // __QUICK_SORT_H__

源文件

```#include "quick_sort.h"

void quickSortV1(int32 arr[], int32 R)
{
    FUNCTION_BGEIN
    processQuickSortV1(arr, 0, R);
    FUNCTION_END
}

int32 partitionV1(int32 arr[], int32 L, int32 R)
{
    FUNCTION_BGEIN
    LOG_TRACE("L : %d,R : %d\n", L, R);
    int32 pivot = arr[R];
    int32 less = L - 1;
    int32 more = R;
    int32 idx = L;

    while (idx < more)
    {
        if (arr[idx] <= pivot)
        {
            swap(arr, idx++, ++less);
        }
        else
        {
            swap(arr, idx, --more);
        }
    }
    // 把最右侧的数和小于等于区域最右侧的下一个数做交换
    swap(arr, R, less + 1);
    FUNCTION_END
    return less;
}

void processQuickSortV1(int32 arr[], int32 L, int32 R)
{

    FUNCTION_BGEIN
    if (L >= R)
    {
        return;
    }
    // 小于区域的右边界
    int32 less = partitionV1(arr, L, R);
    processQuickSortV1(arr, L, less);
    processQuickSortV1(arr, less + 2, R);
    FUNCTION_END
}

void quickSortV2(int32 arr[], int32 R)
{
    FUNCTION_BGEIN
    processQuickSortV2(arr, 0, R);
    FUNCTION_END
}

void processQuickSortV2(int32 arr[], int32 L, int32 R)
{
    FUNCTION_BGEIN
    if( L < R)
    {
        std::vector<int32> vecInt;
        vecInt.clear();
        partitionV2(arr, L, R, vecInt);
        processQuickSortV2(arr, L, vecInt[0]);
        processQuickSortV2(arr, vecInt[1], R);
    }
    FUNCTION_END
}

void partitionV2(int32 arr[], int32 L, int32 R, std::vector<int32>& vecIdx)
{
    FUNCTION_BGEIN
    int32 pivot = arr[R];
    int32 less = L - 1;
    int32 more = R;

    while (L < more)
    {
        if (arr[L] < pivot)
        {
            swap(arr, L++, ++less);
        }
        else if (arr[L] == pivot)
        {
            ++L;
        }
        else
        {
            swap(arr, L, --more);
        }
    }
    swap(arr, more, R);

    vecIdx.push_back(less);
    vecIdx.push_back(more + 1);
    FUNCTION_END
}

12 堆排序

1 堆结构就是用数组实现的完全二叉树结构
2 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4 堆结构的 heapInsert与 heapify操作
5 堆结构的增大和减少
6 优先级队列结构，就是堆结构

什么是完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

完全二叉树的特点

1. 叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1;
2. 出于简便起见,完全二叉树通常采用数组而不是链表存储。
3. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
4. 完全二叉树第i层至多有2*(i-1)个节点，共i层的完全二叉树最多有2*i-1个节点。
5. 只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
6. 对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

判断完全二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

将数据转换成一个完全二叉树

将数组的索引作为二叉树的节点值

根节点索引和子树节点索引满足以下关系
设节点的索引为 $i$
其左子树节点的索引 : $2\times i+1$
其右子树节点的索引 : $2\times i+2$
其父节点的索引为 : $(i-1)/2$

关于堆的两个操作
1 给定数组中某个位置的数,将这个数插入到已构建好的大根堆中 使大根堆依然是大跟堆

/**
 * 将数组中给定位置的数按大根堆的方式插入到堆中
 * @param arr
 * @param index
 */
public static void  heapInsert(int[] arr,int index){
    // 当前数比父节点的数大 就一直与父节点进行替换
    while (arr[index] > arr[(index - 1) /2 ]){
         swap(arr,index,(index - 1) / 2);
         // 来到父位置
         index = (index - 1) / 2;
     }
}

上面的操作可以理解从堆底一直往上蹿 直到遇到不小于它的数 时间复杂度是 $O(lo{g}_2^n)$

从大根堆中返回一个最大值,保证移除最大值之后,剩下的数字依旧是大根堆

调整步骤 : 先返回堆顶的元素,将堆的最后一个元素和堆顶元素做交换,堆的大小减 1
然后对堆顶元素做调整,将堆调整成大根堆,即当存在左子节点,右子节点,或左右子节点都存在时,从左右节点中找到一个最大的值,和堆顶的数字进行比较,如果堆顶数字小,则交换,周而复始

例如 : 存在如下的大根堆,挑出最大值过程如下 :

 
第一步

 
第二步

 
第三步

 
第四步

 
第五步

coding

2 将堆顶的数完成调整,将堆调整成大根堆

/**
* 从指定的位置构建大根堆
* @param arr
* @param index 指定的位置
* @param heapSize 堆中数的个数 空间数据是否属于堆
*/
public static void heapify(int[] arr,int index,int heapSize){
	// 左孩子的索引
	int left = (2 * index) + 1;
	// 存在左子节点
	while (left < heapSize){
	    // 两个子节点中  谁的值大就把索引给谁
	    int largest = (left + 1 < heapSize && arr[left + 1] > arr[left]) 
	    ? left + 1 : left;
	    // 父节点和子节点谁的值大 把值给 largest
	    largest = arr[largest] > arr[index] ? largest : index;
	    // 父节点的值比子节点的值大 不用交换 直接退出
	    if (largest == index){
	        break;
	    }
	    //较大的子节点和父节点进行交换
	    swap(arr,largest,index);
	    index = largest;
	    left = 2 * index + 1;
	}
}

上述操作的时间复杂度也是 $O(lo{g}_2^n)$

堆排序

1 先让整个数组都变成大根堆结构，建立堆的过程 :
  1) 从上到下的方法，时间复杂度为$O(n\times lo{g}_2^n)$
  2) 从下到上的方法，时间复杂度为$O(n)$
2 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，
一直周而复始，时间复杂度为$O(n\times lo{g}_2^n)$
3 堆的大小减小成0之后，排序完成

堆排序的完整代码

import java.util.Arrays;

public class HeapSortTest {
    public static void main(String[] args) {
        int[] arr = {10,3,7,4,6,2,8,90};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

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

    /**
     * 将数组中给定位置的数按大根堆的方式插入到堆中
     * @param arr
     * @param index
     */
    public static void  heapInsert(int[] arr,int index){
        // 当前数比父节点的数大 就一直与父节点进行替换
        while (arr[index] > arr[(index - 1) /2 ]){
             swap(arr,index,(index - 1) / 2);
             index = (index - 1) / 2;
         }
    }

    /**
     * 从指定的位置构建大根堆
     * @param arr
     * @param index 指定的位置
     * @param heapSize 堆中数的个数 空间数据是否属于堆
     */
    public static void heapify(int[] arr,int index,int heapSize){
        // 左孩子的索引
        int left = (2 * index) + 1;
        // 存在左子节点
        while (left < heapSize){
            // 两个子节点中  谁的值大就把索引给谁
            int largest = (left + 1 < heapSize && arr[left + 1] > arr[left]) 
            ? left + 1 : left;
            // 父节点和子节点谁的值大 把值给 largest
            largest = arr[largest] > arr[index] ? largest : index;
            // 父节点的值比子节点的值大 不用交换 直接退出
            if (largest == index){
                break;
            }
            //较大的子节点和父节点进行交换
            swap(arr,largest,index);
            index = largest;
            left = 2 * index + 1;
        }
    }

    public static void heapSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        // 将数组中的所有元素加入大根堆中
        /*for (int  i = 0;i < arr.length;++i){
            heapInsert(arr,i); // O(logN)
        }*/
        for(int i = arr.length - 1;i >= 0; i--){
            heapify(arr,i,arr.length);
        }
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize > 0){// O(N)
            heapify(arr,0,heapSize);// O(logN)
            swap(arr,0,--heapSize);//O(1)
        }
    }
}