精华内容
下载资源
问答
  • 时间复杂度为O(n*logn)的排序算法
    千次阅读
    2019-07-23 18:20:50

    一、时间复杂度为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;
    };
    
    更多相关内容
  • 归并排序 这里用递归实现了归并排序,左边排序-&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);
        }
    
    };
    

     

     

     

     

     

     

    展开全文
  • 时间复杂度 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)
    
    展开全文
  • 时间复杂度为O(logn)的算法

    万次阅读 2018-04-23 19:21:27
    今天被问到了关于时间复杂度的问题,关于O(logn)我还真有点懵,所以找了篇博客学习记录一下。 下面内容转载自https://blog.csdn.net/u011619283/article/details/51878201 典型时间复杂度 我们知道算法的执行...

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

    典型时间复杂度

    我们知道算法的执行效率,可以从它的时间复杂度来推算出一二。而典型的时间复杂度有哪些类型呢?
    典型的时间复杂度.png
    由上图,可以看出,除了常数时间复杂度外,logN型的算法效率是最高的。今天就介绍三种非常easy的logN型算法。

    对分查找

    给定一个整数X和整数A0,A1,…,An-1,后者已经预先排序并在内存中,求是的Ai= X的下表i,如果X不在数据中,则返回i = -1.

    - (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

    * 分析 :*通过上面的程序可以看出,要算出时间复杂度,就是求出while循环的次数。
    mid 每次的取值分别是数组长度(N-1)/2,(N-1)/2/2,(N-1)/2/2/2,…,1,0,-1。那么只用求出2的多少次方等于N-1,再加上可能的多需要的次数2。假设2的f次方等于N-1,最大时间即为log(N-1) + 2。因此对分查找的时间复杂度为logN。再举一个实际的例子,假设最初high = 128,low = 0,则mid的最大取值为64,32,16,8,4,2,1,0,-1。大家可以计算时间。

    欧几里得算法

    第二个是计算最大公因数的欧几里得算法。两个整数的最大公因数Gcd是同时整除二者的最大整数。于是,Gcd(50,15) = 5。

    - (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

    算法超级简单,但是里面还是有一些精髓的。算法假设m>=n,但是如果m < n,则在第一次while循环后,m和n 会互相交换。
    该算法的整个运行时间依赖于确定余数序列的长度,也就是while循环的次数。
    依然举例m = 1989 和n = 1590,则余数序列是399,393,6,3,0。从而,Gcd(1989,1590) = 3。
    虽然看不出余数的值是按照常数引子递减,有时候递减的非常少,例如从399递减到393。但是,我们可以证明,两次迭代以后,余数最多是原始值的一半。迭代次数至多是2logN,所以时间复杂度是logN。
    怎么证明 M > N,则M mod N < M /2呢?
    如果N =< M/2,则由于余数小于N,即M mod N < N <= M/2,所以余数也小于M/2。
    如果N> M/2,则此时M中有个N,从而余数M-N < M/2。

    幂运算

    最后一个算法,是计算一个整数的幂。我们可以用乘法的次数作为运行时间的度量。
    计算X的N次方常见的算法是使用N-1次乘法自乘。但是用递归算法更好。

    - (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

    如果N是偶数,则X的N次方 = X的N/2次方乘以X的N/2次方,如果N是奇数,则X的N次方 = X 的(N-1)/2 次方乘以 X的(N-1)/2次方乘以X。
    显然,所需要的乘法次数最多是2logN。那么时间复杂度就是logN咯。

    展开全文
  • 时间复杂度为O(N*logN)的常用排序算法主要有四个——快速排序、归并排序、堆排序、希尔排序1.快速排序·基本思想 随机的在待排序数组arr中选取一个元素作为标记记arr[index](有时也直接选择起始位置),然后在arr...
  • 各种排序算法时间复杂度对比
  • 常见排序算法时间空间复杂度、稳定性比较 一、排序算法比较 注: 1、归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。 2、 基数排序时间复杂度为O(N*M),其中N数据个数,M数据位数...
  • 算法复杂度O(logn)详解

    2021-05-22 03:05:26
    //时间复杂度为O(1)的程序步骤序列}由于cnt每次在乘以2之后都会更加逼近n,也就是说,在有x次后,cnt将会大于n从而跳出循环,所以\(2 ^ x = n\), 也就是\(x = log_2n\),所以这个循环的复杂度为O(logn)二.典型时间...
  • 算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的...
  • 算法效率度量 1.时间复杂度O(n) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...O(n logn)<...2.空间复杂度 ...常用空间换时间 ...时间复杂度 ...时间复杂度:算法性能指标...常用排序算法及...
  • 各种排序算法时间复杂度

    万次阅读 多人点赞 2019-06-04 13:06:31
    当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,在算法分析时,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。算法中语句的频度不仅与...
  • 排序算法 时间复杂度+空间复杂度 总结
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2017-07-30 21:33:22
    排序算法分类排序算法比较表格填空 排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入...
  • 上一个排序随笔中分析了三种时间复杂度为O(n2)的排序算法,它们适合小规模数据的排序;这次我们试着分析时间复杂O(nlogn)的排序算法,它们比较适合大规模的数据排序。1 归并排序1.1 原理将待排序列划分前后两...
  • 归并排序、快速排序都使用了分治的思想,时间复杂度都是O(N*logN)。由于其时间复杂度低,所以被广泛的应用,比如Java Collection.sort; Mysql数据库中的排序;Tim排序等。
  • 常见排序算法及其时间复杂度

    万次阅读 多人点赞 2019-06-20 18:00:18
    常见排序算法及其时间复杂度 一、内部排序:1.稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序的实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序的实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并...
  • 常见排序算法及其时间复杂度(超详细)

    万次阅读 多人点赞 2019-09-19 23:15:44
    稳定的排序算法 稳定的排序 时间复杂度 空间复杂度 冒泡排序(bubble sort) 最差、平均都是O(n^2),最好是O(n) 1 插入排序(insertion sort) 最差、平均都是O(n^2),最好是O(n) 1 归并排序(merge sort) 最差、平均、...
  • 八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码...
  • 归并排序,其实就是递归+合并。
  • 排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序,本文讲的都属于内排序。 内排序有可以分为以下几类: ...
  • 描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法时间复杂度, 它们代表的含义: 这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。大O加上()的形式,里面...
  • 排序算法之 冒泡排序及性能优化(时间复杂度+空间复杂度分析) 排序算法之 简单选择排序及时间复杂度分析 排序算法之 直接插入排序及时间复杂度分析 排序算法之 希尔排序及时间复杂度分析 排序算法之 快速排序及时间...
  • 时间维度:是指执行当前算法所花费的时间,我们通常用「时间复杂度」来描述。 空间复杂度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 时间维度 O(n) for(var i = 0; i < n;...
  • 排序算法时间复杂度比较

    千次阅读 2019-01-27 08:53:46
    各种排序算法比较 一、基本排序算法 冒泡排序 假如我们现在按身高升序排队,一种排队的方法是:从第一名开始,让两人相互比身高,若前者高则交换位置,更高的那个在与剩下的人比,这样一趟下来之后最高的人就站到...
  • 本文通过二分查找和并归排序为例,主要介绍时间O(logn)和O(nlogn)这两个时间复杂度是怎么得出来的。O(1)、O(n)、O(n2)在此不做介绍了,O(n)、O(n2)就是for循环一次、二次,O(1)的话…就好像单例模式或者map吧。 首先...
  • 时间复杂度 空间复杂度       稳定性           关联性        最好          最差        平均  ...
  • 这是使用desmos画出来的图形。...)低于xlog(x)高于x,但通常我们的排序算法快排和归并的最优是xlog(x)最坏是n^2, 通过二分查找改进的排序算法最坏是log(n!),最好是n。 虽然nlog(n)和log(n!)相差不...
  • C/C++中四种排序算法时间空间复杂度 一.浅谈时间复杂度和空间复杂度 1.概念: 时间复杂度:就是说执行算法需要消耗的时间长短,越快越好。 空间复杂度:就是说执行当前算法需要消耗的存储空间大小,也是越少越好。...
  •  快速排序是排序算法中效率相对较高的,但使用的人却是比较少,大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观,容易理解,而快速排序使用到了递归,大家可能就有点不知所措了。 算法分析  快速...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,880
精华内容 18,352
关键字:

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