归并排序

这里用递归实现了归并排序，左边排序->右边排序->让其整体有序。

让其整体有序的过程中使用了排外序的方法。即构造一个新的数组，比较对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);
    }

};

时间复杂度 O(N*logN)：
归并排序，堆排序（大根堆，小根堆，heapInsert/heapify)，快速排序（荷兰国旗问题）。

1. 归并排序
   L — Mid — R
   先让 左有序，右有序。
   归并 谁小copy谁

def mergeSort(data):
	def mergeSortFunc(data, L, R):
		if L==R:
			return 
		mid = L+(R-L)//2
		mergeSortFunc(data, L, mid) //左部分 merge sort
		mergeSortFunc(data, mid+1, R)//右部分 merge sort
		merge(data, L, R, mid) // 左右 merge
		
	def merge(data, L, R, M):
		help_arr = []
		p1 = L
		p2 = M+1
		while p1<=M and p2<=R:
			if data[p1] <= data[p2]:
				help_arr.append(data[p1])
				p1++
			else:
				help_arr.append(data[p2])
				p2++
		while p1<=M:
			help_arr.extend(data[p1:M+1])
		while p2<R:
			help_arr.extend(data[p2:R+1])
		data[L:R+1] = help_arr
	
	if len(data) < 2:
		return
	
	mergeSortFunc(data, 0, len(data)-1)
	

T(N) = 2T(N/2) +O(N) 所以 时间复杂度就是 O(N*logN)， 额外空间复杂度是 O(N)

题目：小和问题 和 逆序对问题

小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。

//解法: 暴利查询  每个数查询左侧比他小的值 并且求和， 时间复杂度O(N^2)

//解法2： 归并。
一个数a 左边比他小的数加和 产生小和  与 右边有多少个比他大产生 n*a 小和 等价.
'''
例：  1 3 4 2 5
划分左右  1 3 4      2 5
划分左右 1 3    4   2    5
merge 时 右侧比 左侧大的时候 产生小和。

1 3 merge：1<3 , 右侧有1个比1 大。所以 1* 1
13  4 merge: 1<4，右侧有1个比1大， 产生1*1,  3和4比较， 3<4，右侧有1个比3大，产生1*3.
得到 1 3 4 

2 5 merge: 2 < 5， 右侧有1个比2大，所以产生1*2
得到2 5

134 25 merge：
--> 1 < 2： 右侧有2个比1大， 产生2*1.  新的数组得到 1. 原数组为 34  25
--> 3 > 2: 不产生小和。新的数组为 1 2，原数组为 34 5
--> 3 < 5: 右侧有1个比3大， 产生1*3. 新数组得到 1 2 3， 原数组为4 5
--> 4 < 5: 右侧有1个比4大， 产生1*4. 新数组为 1 2 3 4 5. 

最后产生的小和： 1*1 + 1*1 + 1*3 + 1*2 + 2*1 + 1*3 + 1*4 = 16

merge 实质：让左侧的数 依次碰到每一个右侧的数。 每一次搞定的左侧 不需要重复求，并且计算右侧有多少个比当前数大的时候 可以通过下标直接计算得到 不需要一个个数，因为左侧和右侧都是有序的，当左侧小于右侧的时候 产生小和。   
merge sort 好的地方在于 每次比较结果都是变成有序序列。后续比较 只需要左组 和右组进行比较，不需要组内比较， 只需要跨组比较。

暴利查询：1： 左侧小于1的 无。  
		3： 左侧小于3的 1， 
		4： 左侧小于4的1，3，
		2： 左侧小于2的1
		5： 左侧小于5的1，2,3,4 
		加和： 1+1+3+1+1+2+3+4 = 16
'''
def leastSum(data):
	def mergeSort(data, L, R):
		if L==R:
			return 0
		mid = L+(R-L)//2
		return mergeSort(data, L, mid) 
			+ mergeSort(data, mid+1, R) 
			+ mergeAndSum(data, L, R, mid)
	def mergeAndSum(data, L, R, Mid):
		p1 = L
		p2 = Mid+1
		help_arr = []
		ret = 0
		while p1 <= Mid and p2 <= R:
			if data[p1]< data[p2]:
				help_arr.append(data[p1])
				ret += (R-p2+1)*data[p1]
				p1++
			else data[p1]>=data[p2]://相等的时候 copy 右部分。
				help_arr.append(data[p2])
				p2++
		while p1<=Mid:
			help_arr.extend(data[p1:Mid+1])
		while p2<=R:
			help_arr.extend(data[p2:R+1])
		data[L:R+1] = help_arr
		return ret
	//leastSum func				
	if len(data)<2：
		return
	return mergeSort(data, 0, len(data)-1, ret)
	

逆序对：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。（即求每个数 左边多少个比它大的数）

def reverseData(data):
	if len(data)< 2:
		return
	def mergeSort

2. 堆

   堆：用数组实现的完全二叉树结构（默认下标从0开始）
   0 1 2 3 4 5 6 7
   –> 0
   1 2
   3 4 5 6
   完全二叉树： 结点i, 父节点 (i-1)/2 左孩子： 2i +1， 右孩子： 2i+2

   大根堆：对于每颗子树的最大值 就是 父节点
   小根堆：对于每颗子树的最小值 就是父节点

   heapsize 是堆的一个重要参数。

   任何一个数组 都可以按照大根堆的方式进行排序。 时间复杂度为O(Log_2 N)

def heapInsert(data, index): //数字 来到了 index 位置，如何往上移动
	while data[index] > data[(index-1)//2]:
		data[index], data[(index-1)//2] = data[(index-1)//2],data[index]
		index = (index-1)//2
	// 即包含了index在0位置 没有父节点的时候  也包含 index在其他位置 有父节点的时候
	// index = 0 时， (index-1)//2  也等于0

如果用户跟我要数的时候，比如要大根堆的堆顶，但是剩下的还是希望是大根堆结构。如何做？
用最后一个位置填堆顶，heapsize 减1，相当于把最后一个位置在堆里面移除。此时需要调整为大根堆，也就是把堆顶往下调整。

时间复杂度为O(Log_2 N)

def  heapify(data, index, heapSize):
	left = index * 2 + 1 //左孩子下标
	while left < heapSize： //下方还有孩子的时候
		if left+1 < heapSize and data[left+1] > data[left]:
			largest = left+1
		else:
			largest = left
		if data[largest] < data[index]:
			largest = index
			break
		data[largest], data[index] = data[index], data[largest]
		index = largest
		left = index*2 + 1

如果某个位置的值发生了变化，则可以heapInsert 和heapify 各来一遍，最多只可能发生一个函数操作。

3. 堆排序

   给定一个数组，先把数组整体变成大根堆，此时heapsize=N。

   比如： 9 8 3 7 6 2 1
   step-1: 建立大根堆
   step-2:把堆顶 和最后一个位置交换。把最后一个位置去掉。heapSize-1
   step-3: 调整当前的数组为大根堆。

   如果数组放那边，调整成大根堆 可以自顶往上(时间复杂度为O(logN))，也可以自底往上（时间复杂度度O(N)）。
   自底往上把数组调整成大根堆。一开始认为数组为一个完全二叉树，从最后一个数开始 调整为大根堆（看他是否比每一个子孩子大，如果是的话 就往下走）heapify

   堆排序：时间复杂度为O(NlogN), 额外空间复杂度O(1)

//从顶往下
def heapSort(data):
	if len(data)<2:
		return
	for i in range(0, len(data)):
		heapInsert(data[i],i)
	heapSize = len(data)-1
	data[0],data[heapSize] = data[heapSize],data[0]
	while heapSize>0:
		heapify(data,0,heapSize)
		data[0],data[heapSize] = data[heapSize],data[0]

4. 堆扩展
   已知一个几乎有序的数组，几乎有序是指的是 如果把数组排好顺序的话，每个元素一定的距离可以不超过K， 并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数组排序。
   答： 使用堆。 为什么？

   如何用？
   先把0-（K+1）个数 设置为小根堆，也就是0位置放最小的。
   然后再把1-（K+2）个数 设置为小根堆，得到1的位置。
   。。。
   时间复杂度O(N * log K) (小根堆调整是log K 级别的)

5. 快速排序

   5-1：快排的partition的思想

   问题1： 给定一个数a，和数组A，请先做到 把小于等于a的放到左边，大于a的放到右边。要求时间复杂度O(N)，额外空间复杂度O(1)。
   方法：
   设一个小于等于 区域。最开始为空。
   当前数 <= a, 当前数和小于等于区域下一个数 交换，然后小于等于区域阔一个位置，当前数跳到下一个。
   当前数 >a, 当前数直接跳下一个。
   需要有的参数：小于等于区域指针，当前数指针。

   问题1拓展：荷兰国旗问题。小于a的放到左边，等于a放中间，大于a的放右边。
   方法：
   当前数=划分值， 当前数跳到下一个
   当前数<划分值，当前数 与小于区域 下一个数 交换，小于区域 往后扩一个，当前数跳到下一个
   当前数>划分值，当前数与大于区域 前一个数 交换，大于区域往前扩一个，当前不变。
   当前数与大于区域撞上时，停止。

   小于划分值区域 等于区域 当前数 …（待定区域） 大于区域

def NetherLandsFlag(data,p):
	def partition(data, L, R, p):// p是划分值，要把L-R区间调整
		less = L-1 //小于区域的右边界
		more = R + 1//大于区域的左边界
		while L< more： // L是当前数下标
			if data[L] < p：//小于划分值
				data[L], data[less+1] = data[less+1], data[L]//交换
				less++
				L++
			else if data[L]> p：
				data[L], data[more-1] = data[more-1], data[L]
				more--
			else:
				L++
		return [less+1, more-1] //等于区域的下标
	if len(data)<1:
		return
	partition(data, 0, len(data)-1, p)

5-2：快排
不改进的快速排序：
1) 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成3个部分：左侧<划分值，中间==划分值，右侧>划分值。
2)对左侧范围和右侧范围，递归执行。

分析：
1）划分值越靠近两侧，复杂度越高，划分值越靠近中间，复杂度越低.
2）可以轻而易举地举出最差的例子，所以不改进的快排时间复杂度是O(N^2) （比如：1,2,3,4,5,6 划分值是6）。最好的情况是partition 的位置几乎在中点,时间复杂度O(NlogN)。
3）为了防止每次都是最差的情况出现，则通过L-R上随机选择一个数和N-1位置交换，这样降低复杂度。 (因为随机选择一个数，所以各种情况都是均等的，最后平均复杂度为O(NlogN))

经典快排：
(L-R上随机选一个数字和N-1位置上的数进行交换）X 在N-1位置上，对0-N-2上的数进行partition <=x, >x (<=x 左侧，>x 右侧，然后把x和>x区域的第一个数交换)，保证小于等于区域最后一个数是x.这样对于<=区域继续递归，然后对>x区域递归。 Base case: 区域只有一个值时 不需要排序。
（最差的情况 时间复杂度O(N^2)，空间复杂的O(N)，最好的情况是时间复杂度O(N*logN)，空间复杂度O(logN)）

改进的快排：
（L-R上随机选一个数字和N-1位置上的数进行交换）X是N-1上的划分值，在0 - (N-2)上进行荷兰国旗加速 <x， =x， >x（得到3个区域），然后把X和大于区域第一个值交换，并且大于区域往后移一位。然后在<x 和>x 区域分别做递归.

改进VS 经典快排：
改进的快排是每次排序 可以把所有等于x的都搞定 ，而经典的快排是每次都只能搞定一个数(也就是只有最后那个划分值 放到正确的位置)

def quickSort(data):
	def partition(data, L, R)://
		less = L-1
		more = R // 最后一个作为划分值
		while L < more:
			if data[L] < data[R]:
				data[L], data[less+1] = data[less+1],data[L]
				L++
				less++
			else if data[L] > data[R]:
				data[L], data[more-1] = data[more-1],data[L]
				more-- 
			else:
				L++	
		data[more-1], data[R] = data[R],data[more-1]
		return (less+1, more)
	def q_sort(data, L, R)://排好L-R之间的数
		if L<R:
			index = random(L, R)
			data[R], data[index] = data[index], data[R]
		p = partition(data, L, R)
		q_sort(data, L, p[0]-1)
		q_sort(data, p[1]+1, R)
	
	if len(data)<2:
		return
	q_sort(data, 0, len(data)-1)

今天被问到了关于时间复杂度的问题，关于O(logn)我还真有点懵，所以找了篇博客学习记录一下。
下面内容转载自https://blog.csdn.net/u011619283/article/details/51878201

- (int)BinarySearch:(NSArray *)originArray element:(int)element
{
    int low, mid, high;
    low = 0; high = (int)originArray.count - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if ([originArray[mid] intValue] < element) {
            low = mid + 1;
        } else if ([originArray[mid] intValue] > element) {
            high = mid -1;
        } else {
            return mid;
        }
    }
    
    return -1;
}
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

- (unsigned int)Gcd:(unsigned int)m n:(unsigned int)n
{
    unsigned int Rem;
    while (n > 0) {
        Rem = m % n;
        m = n;
        n = Rem;
    }
    return m;
}
   
1
2
3
4
5
6
7
8
9
10

- (long)Pow:(long)x n:(unsigned int)n
{
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    
    if ([self isEven:n]) {
        return [self Pow:x * x n:n / 2];
    } else {
        return [self Pow:x * x n:n / 2] * x;
    }
}

- (BOOL)isEven:(unsigned int)n
{
    if (n % 2 == 0) {
        return YES;
    } else {
        return NO;
    }
}
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24