精华内容
下载资源
问答
  • 一、时间复杂度为O(n*logn的排序算法 二、今日刷题 一、时间复杂度为O(n*longn)的排序算法 1、归并排序: 排序的思想:就是不断分成两部分:左边和右边,分别将左边和右边有序之后才进行合并得到最后的有序的...

    一、时间复杂度为O(n*logn)的排序算法

    二、今日刷题

    一、时间复杂度为O(n*longn)的排序算法

    1、归并排序:
    排序的思想:就是不断分成两部分:左边和右边,分别将左边和右边有序之后才进行合并得到最后的有序的数组。


    时间复杂度:o(n*logn)。


    核心:归并排序之所以能达到o(n*logn)的时间复杂度,主要原因是其避免了很多不必要的排序,当保持左边和右边部分有序之后,其进行合并的时候进行比较的是不同组的元素之间的比较,组内的元素不再进行比较。

    代码:

    void merge(int a[], int l, int mid, int r)
    {
    	int* help = new int[r - l + 1];//辅助数组
    	int p1 = l;
    	int p2 = mid + 1;
    	int k = 0;
    	while (p1 <= mid&&p2 <= r)
    	{
    		if (a[p1] <= a[p2])
    		{
    			help[k++] = a[p1];
    			p1++;
    		}
    		else
    		{
    			help[k++] = a[p2];
    			p2++;
    		}
    	}
    	while (p1 <= mid)
    		help[k++] = a[p1++];
    	while (p2 <= r)
    		help[k++] = a[p2++];
    	int len = r - l + 1;
    	for (int i = 0; i < len; ++i)
    		a[l + i] = help[i];
    	delete[] help;
    	//cout << "hello" << endl;
    }
    void mergesort(int a[], int l, int r)
    {
    	if (l == r)
    		return;
    	int mid = l + ((r - l) >> 1);
    	mergesort(a, l, mid);
    	mergesort(a, mid + 1, r);
    	merge(a, l, mid, r);
    }
    

    例题:最小和问题和求逆序对,以最小和问题为例进行分析:

    最小和问题:最小和也就是每个数的左边比其小的数的和,再将数组中所有的该和进行累加的结果,例如数组{3,5,2,6},a[0]左边没有比起小的,a[1]左边比其小的为3,a[2]左边比其小的没有,a[3]左边比其小的有3,5,2,所以数组的最小和为0+3+0+3+5+2.

    分析:求最小和可以转化为求一个数的右边有多少个比其大的数,有几个那么其就贡献了几次最小和。求一个数右边有多少个比其大的使用归并排序的思想。在归并排序的merge的时候进行求解,核心思想是归并后的部分内部不必进行计算,只有不同部分之间才涉及计数;当出现相等的值的时候,先防止右边的数。

    代码:

    int merge(int a[], int l, int mid, int r)
    {
    	int* help = new int[r - l + 1];//辅助数组
    	int p1 = l;
    	int p2 = mid + 1;
    	int k = 0;
    	int res = 0;
    	while (p1 <= mid&&p2 <= r)
    	{
    		if (a[p1] < a[p2])//左边的数字小,参与贡献
    		{
    			help[k++] = a[p1];
    			res += (r - p2 + 1)*a[p1];
    			p1++;
    		}
    		else//左边的数字大,那么就不参与贡献
    		{
    			help[k++] = a[p2];
    			p2++;
    		}
    	}
    	while (p1 <= mid)
    		help[k++] = a[p1++];
    	while (p2 <= r)
    		help[k++] = a[p2++];
    	int len = r - l + 1;
    	for (int i = 0; i < len; ++i)
    		a[l + i] = help[i];
    	delete[] help;
    	return res;
    	//cout << "hello" << endl;
    }
    int mergesort(int a[], int l, int r)
    {
    	if (l == r)//递归结束的条件,注意不要忽略
    		return 0;
    	int mid = l + ((r - l) >> 1);
    	return mergesort(a, l, mid)+mergesort(a, mid + 1, r)+merge(a, l, mid, r);
    	//这行代码的理解个人觉得很重要
    	//首先将可以直接将左边家上右边再加上总体合并的,可以直接将merge(a,l,mir,r)相加的原因是
    	//同一个部分内部已经求解过了,也就是mergesort的部分,那么现在值涉及不同部分之间,所以直
    	//接加上不同部分合并的结果即可
    }
    

    2、堆排序(以大根堆为例)

    堆结构其实就是一个数组,只不过将该数组视为一棵完全二叉树,对于数组中下标为i的节点,其左孩子的下标为2i+1,右孩子的下标为2i+2(数组的下标从0开始),父亲节点的下标为(i-1)/2。
    堆结构中重要的操作有两个:heapinsert和headpify。heapinsert是指我们在堆中插入一个新的数字的时候,也就是在数组的末尾新增一个数字的时候将数据变成堆。
    heapify是将堆顶元素删除,将剩下的数据重新变为堆。

    小技巧:由于数组的长度和数据的数量一般是固定的,所以我们可以使用一个单独的变量heapsize来指定堆的大小。

    代码:

    void heapinsert(int a[], int index)//在数组的index位置上新增加一个数
    {
    	while (a[index] > a[(index - 1) / 2])//这里已经考虑了边界条件,如果是到0,那么0和0自己比较就会跳出循环
    	{
    		int tmp = a[index];
    		a[index] = a[(index - 1) / 2];
    		a[(index - 1) / 2] = tmp;
    		index = (index - 1) / 2;
    	}
    }
    
    void heapify(int a[], int index,int size)
    {
    	int left = index * 2 + 1;
    	int largest;
    	//在进行操作之前先判断是否有左孩子和右孩子
    	while (left < size)
    	{
    		int largest = left + 1 < size&&a[left + 1] > a[left]?left + 1 : left;
    		largest = a[largest]>a[index] ? largest : index;
    		if (largest == index)
    			break;
    		int tmp = a[largest];
    		a[largest] = a[index];
    		a[index] = tmp;
    		index = largest;
    		left = index * 2 + 1;
    	}
    }
    
    

    堆排序:有了上述的操作之后,堆排序就简单了,我们使用heapinsert逐个将数组的元素加入堆,也就是不断扩大对的大小,将数组符合最大堆的情况。然后每次将堆顶取出,之后用最后的元素代替该元素,然后在heapify将剩下的又调整成最大堆,每次都得到最大值,所以最后得到的就是从大到小排好序的。

    进行数组的更新:如果要进行数组的更新,那么先看看能不能heapinsert,之后看能不能headpify。

    由给定数组建堆:
    方法一:时间复杂度为o(nlogn),这对数组中的数据是一个一个给的或者是一次性给的都适用,具体的方法就是对每一个数组中的数字从头到尾进行heapinsert。
    方法二:时间复杂度为o(logn),这只针对的是数组是一次性给定的,我们先假定给定的数组就是一个大根堆,然后对堆中的每一个位置进行heapify,也就是判断自己与其子树是否构成大根堆,那么最底层有n/2个结点,其向下的层数就是其本身,倒数第二层有n/4,其操作2层……那么总的就是n/2+n/4
    2+n/8*3……,最后求的复杂度为o(n)。

    函数类库提供的堆:在C++中我们可以使用优先级队列,其就是一个堆:

    //默认的就是大根堆
    priority_queue<int> a;
    //小根堆要指明比较其
    priority_queue<int,vector<int>,greater<int> > b;
    

    例题:
    题目:已知一个几乎有序的数组,几乎有序是指如果把数组排好顺序的话,每个元素移动的距离不超过k,并且k相对于数组来说比较小。请选择一个适合的排序算法针对这个数据进行排序。
    思路:使用小根堆(大根堆也是可以的),首先将0到k的k+1个数进入小根堆,由于距离不超过k,所以到0位置上的数一定在这个k+1个数之间,然后在对1到k+2上的数进小根堆得到的堆顶就是1位置上的数,依次就可以得到最后有序的数组。
    时间复杂度:每次调整堆的时间复杂度为o(logK),一共有n个数,所以总的时间复杂度为o(n*logK)。
    代码:

    void sortedArrayDistanceLessK(vector<int> a, int k)
    {
    	priority_queue<int, vector<int>, greater<int> > heap;
    	int len = a.size();
    	//先将0到k-1的数组进堆
    	int index = 0;
    	for (; index < min(len, k); index++)
    		heap.push(a[index]);
    	int i = 0;
    	for (; index < len; i++, index++)
    	{
    		heap.push(a[index]);
    		a[i] = heap.top();
    		heap.pop();
    	}
    	while (!heap.empty())
    	{
    		a[i++] = heap.top();
    		heap.pop();
    	}
    
    }
    
    

    3、快排之partition:
    快排的核心思想就是partition,而所谓partition也就是给定一个数组和一个值,将数组小于给定值的放在数组的左边,大于该值的放在数组的右边。要求时间复杂度为o(n),空间复杂度为o(1)。

    思路:设置一个小于等于区域,对于数组的当前的数,如果其小于等于给定的数那么其就与小于等于区域的下一个数交换,否则直接跳下一个数。从数的位置可以直观理解:数组中的数:小于等于区域---->大于区域----->当前的值。

    例题:给定数组和一个值,将小于该值的放在数组的左边,等于该值的放在数组的中间,大于该值的放在数组的右边。
    思路:仍然指定小于区域,等于区域和大于区域;当前的值如果小于给定的值,那么就让其与小于区域的下一个数交换,并且将当前值前进一个数;如果当前值等于给定值直接将当前值前进一个数;如果大于将当前值与大于区域的前一个值交换,当前的位置不变。从数组的位置直观理解就是:小于区域的值------>等于区域的值------->当前值------->大于区域的值。
    代码:

    void partition(int a[], int l, int r,int label)
    {
    	int less = l - 1;
    	int more = r + 1;
    	int tmp;
    	while (l < more)//当当前的位置和大于区域相遇的时候结束
    	{
    		if (a[l] < label)
    		{
    			tmp = a[l];
    			less++;
    			a[l] = a[less];
    			a[less] = tmp;
    			l++;
    		}
    		else if (a[l]>label)
    		{
    			tmp = a[l];
    			more--;
    			a[l] = a[more];
    			a[more] = tmp;
    			//当前位置不变
    		}
    		else
    			l++;
    	}
    }
    

    二、今日刷题

    题目:用两个栈实现一个队列的功能
    思路:队列和栈之间的区别在于,队列是先进先出,栈是后进先出。这里两个栈为s1和s2,实现队列的出队列功能:s1如果有元素的话,就将s1的元素压倒s2中,然后弹出s2栈顶的元素,如果s1是空s2有元素,那么直接弹出s2栈顶的元素;如果两个都是空的,那么报错。实现入队列,如果s2中有元素,先将s2中的元素入到s1中,然后再将新的元素push进s1中,否则直接push进s1,代码为:
    class Solution
    {
        //push的时候如果s2是空的,那么直接push进s1,如果s2非空,那么就要先将s2中的元素push如s1
        //pop的时候,如果s2非空,那么直接pop,如果s2为空,那么将s1中的push如s2,然后再pop
    public:
        void push(int node) {
            int tmp;
            if(!s2.empty())
            {
                tmp = s2.top();
                s2.pop();
                s1.push(tmp);
            }
            s1.push(node);
        }
    
        int pop() {
            int tmp;
            if(!s2.empty())
            {
                tmp = s2.top();
                s2.pop();
                return tmp;
            }
            else if(s1.empty())
            {
                cout<<"erroe!";
                return -1;
            }
            else
            {
                while(!s1.empty())
                {
                    tmp = s1.top();
                    s1.pop();
                    s2.push(tmp);
                }
                tmp = s2.top();
                s2.pop();
                return tmp;
            }
        }
    
    private:
        stack<int> s1;
        stack<int> s2;
    };
    
    展开全文
  • 时间复杂度 O(N*logN): 归并排序,堆排序(大根堆,小根堆,heapInsert/heapify),快速排序(荷兰国旗问题)。 归并排序 L — Mid — R 先让 左有序,右有序。 归并 谁小copy谁 def mergeSort(data): def ...

    时间复杂度 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)<2return
    	return mergeSort(data, 0, len(data)-1, ret)
    	
    

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

    def reverseData(data):
    	if len(data)< 2:
    		return
    	def mergeSort
    
    1. 堆:用数组实现的完全二叉树结构(默认下标从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 各来一遍,最多只可能发生一个函数操作。

    1. 堆排序

      给定一个数组,先把数组整体变成大根堆,此时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]
    
    1. 堆扩展
      已知一个几乎有序的数组,几乎有序是指的是 如果把数组排好顺序的话,每个元素一定的距离可以不超过K, 并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数组排序。
      答: 使用堆。 为什么?

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

    2. 快速排序

      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(N
    logN))

    经典快排:
    (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)
    
    展开全文
  • 归并排序 这里用递归实现了归并排序,左边排序-&gt;右边排序-&gt;让其整体有序。 让其整体有序过程中使用了排外序方法。即构造一个新数组,比较对i, j所指向数字进行大小比较,如果arr[i] &gt...

    归并排序

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

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

     

     

     

     

     

     

    展开全文
  • 归并排序 1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ ...

    归并排序

     1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode* sortList(ListNode* head) {
    12         //排序算法 空间复杂度N*logN
    13         //归并排序
    14         if(!head||!(head->next)){
    15             return head;
    16         }
    17         ListNode* slow = head;
    18         //让slow比最终的位置慢一步
    19         ListNode* fast = head->next;
    20         ListNode* temp;
    21         while(fast&&(fast->next)){
    22             if(fast->next->next){
    23                 slow = slow->next;
    24                 fast = fast->next->next;
    25             }else{
    26                 //slow = slow->next;
    27                 fast = fast->next;
    28             }
    29             
    30         }
    31         //将前半段的与后半段分开
    32         temp = slow;
    33         slow = slow->next;
    34         temp->next = NULL;
    35        // return head;
    36         return Merge(sortList(head),sortList(slow));
    37     }
    38     ListNode* Merge(ListNode* L1,ListNode* L2){
    39         ListNode cur(0);
    40         ListNode* temp = &cur;
    41         while(L1&&L2){
    42             if((L1->val)<=(L2->val)){
    43                 temp->next = L1;
    44                 L1 = L1->next;
    45             }else if((L1->val)>(L2->val)){
    46                 temp->next = L2;
    47                 L2 = L2->next;
    48             }
    49             temp = temp->next;
    50         }
    51         if(L1){
    52             temp->next = L1;
    53         }else{
    54             temp->next = L2;
    55         }
    56         return cur.next;
    57     }
    58 };

     

    实现过程

        归并排序算法:

    1、首先将链表进行切分。在我们的算法中,使用两个指针fast和slow,fast的遍历速度是slow指针的两倍。所以当fast遍历到链表的末尾时,slow恰好找到了链表的最中间位置,(这是使用链表存储相对于数组比较麻烦的地方,没办法直接选取最中间的值)。

    2、使用head和slow将链表分成两个子链表,然后继续1中操作,将子链表再分成两部分。直到每个子链表只含有一个元素为止

    3、然后我们将两个子链表进行合并,生成含有2个元素排好序的链表,再将含有2个元素的子链表合并生成4个元素的链表。。。以此类推直到生成一个排好序的新链表。

    注意:合并两个都排好序的链表时,我们只需要遍历一遍,时间复杂度为O(N)。

    例如:

    7   ->  3   ->   9   ->   6    ->   2   ->   8   ->   4   ->   1   -> null

    \    /                 \     /                 \      /              \    /

    3->7->null    6->9->null        2->8->null        1->4->null

            \           /                                 \               /

    3->6->7->9->null                          1->2->4->8->null

                    \                                    /

                  1->2->3->4->6->7->8->9->null

    转载于:https://www.cnblogs.com/timesdaughter/p/5512700.html

    展开全文
  • 时间复杂度为O(N*logN)常用排序算法主要有四个——快速排序、归并排序、堆排序、希尔排序1.快速排序·基本思想 随机在待排序数组arr中选取一个元素作为标记记为arr[index](有时也直接选择起始位置),然后在arr...
  • 1、归并排序 1 void mergeSort(vector<int>& nums,int start,int end){ 2 if(start<end){ 3 int q = (start+end)/2; 4 mergeSort(nums,start,q); 5 ...
  • 快速排序平均时间复杂度是N*logN,同时其也是实践已知最快通用排序算法,但是其最坏情况的时间复杂度依然是N平方,但是只要我们对快速排序算法稍作修改,就可以保证其最坏情况的时间复杂度也是N*logN。...
  • 时间复杂度为o(n)的排序算法:不是基于比较的排序算法;思想来自于桶排序!比如:计数排序和基数排序。其中基数排序中是分别基于个位、十位以及等等更高的位将数据放入桶中,然后再将数据倒出来! 八个经典排序...
  • 本文讲述时间复杂度为n*logn的排序算法:归并排序、快速排序、堆排序以及希尔排序的原理、Java实现以及变形应用。一、归并排序原理:把两个有序数列合并为一个有序数列。需递归实现。Java实现:1 public int[] ...
  • 对经典排序方法性能进行总结: 排序方法 时间复杂度 空间复杂度 稳定性 ...冒泡排序 ...插入排序 ...选择排序 ...归并排序 O( n*logn ) ...堆排序 ...今天重点讨论这三个时间复杂度为O(n*logn)的算法,桶排序
  • 本文讲述时间复杂度为n*logn的排序算法:归并排序、快速排序、堆排序以及希尔排序的原理、Java实现以及变形应用。 一、归并排序 原理:把两个有序数列合并为一个有序数列。需递归实现。 Java实现: 1 ...
  • 本文讲述时间复杂度为n*logn的排序算法:归并排序、快速排序、堆排序以及希尔排序的原理、Java实现以及变形应用。 一、归并排序  原理:把两个有序数列合并为一个有序数列。需递归实现。 Java实现: 1 ...
  • 1、常见的时间复杂度 (1)O(1):常量阶,运行时间常量 (2)O(logn):对数阶,如二分搜索算法 (3)O(n):线性阶,如n个数内找最大值 (4)O(nlogn):对数阶,如快速排序算法 (5)O(n^2):平方阶,如选择排序,...
  • 题目描述 定义:把一个数组最开始若干个元素搬到数组末尾,我们称之为数组旋转。...要求时间复杂度为O(logn),首先我们想到是二分法。 mid = low + (high - low)/2 我们接下来需要考虑三种情况: 1. 第一
  • 时间维度:是指执行当前算法所花费时间,我们通常用「时间复杂度」来描述。 空间复杂度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 时间维度 O(n) for(var i = 0; i < n;...
  • 建堆是通过父节点和子节点两两比较并交换得到时间复杂度为O(n),调整堆需要交换n-1次堆顶元素,并调整堆,调整堆过程就是满二叉树深度logn,所以时间复杂度为O(nlogn),所以最终时间复杂度为O(nlogn)...
  • 比较排序算法的时间复杂度是O(nlogn)证明: 排序算法的比较是两两进行,所以可以抽象成一棵二叉树,相互比较数分别是左右叶子结点,,比较结果存储在父节点中,依此类推。那么算法的时间复杂度就是取决于树...
  • 算法的时间复杂度排序 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(nk) < O(2n) 注意:这里的logn以2
  • 详情参见:... 补充1: 插入排序举例: ...文件初态基本有序时,用直接插入排序,表插入排序,冒泡排序效果最好。...快速排序的空间复杂度为O(logn),时间复杂度为(n*logn);归并排序的空间复杂度为O(n)...
  • #include #include typedef int ... } 输入: 5 3 2 1 -1 -1 -1 4 -1 -1 7 6 -1 -1 -1 输出: 输出lsize: 1:0 2:1 3:2 4:0 5:4 6:0 7:1 第1小是1 第2小是2 第3小是3 第4小是4 第5小是5 第6小是6 第7小是7

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,003
精华内容 401
关键字:

时间复杂度为logn的排序算法