精华内容
下载资源
问答
  • 高效排序算法

    2010-08-28 18:51:00
    已知最大值的高效排序算法 今天看到一个排序算法,感觉挺有新意,可能是我见识短。所以要转到自己博客里。文章分类:Java编程有一组数据3,5,9,7,4,13,15,0,2,20.已知最大数是20,把数据从小到大排序,而且算法...

    已知最大值的高效排序算法

    今天看到一个排序算法,感觉挺有新意,可能是我见识短。所以要转到自己博客里。

    文章分类:Java编程
    有一组数据3,5,9,7,4,13,15,0,2,20.已知最大数是20,把数据从小到大排序,而且算法复杂度只能是1,不能用Java提供的类实现,如Arrays.sort()等。


    思路:

    最大是20,就用一个长度21的boolean数组,把数作为index标记出现过的。然后从小到大遍历这个boolean数据形成排序后的数组

    代码:
    Java代码 复制代码
    1. int[] a = {3,5,9,7,4,13,15,0,2,20};   
    2. boolean[] b = new boolean[21];   
    3.   
    4. for(int i=0;i<a.length;i++) {   
    5.   b[a[i]] = true;   
    6. }   
    7.   
    8. for(int i=0;i<b.length;i++) {   
    9.   if(b[i]) {   
    10.     System.out.print(i+",");   
    11.   }   
    12.   
    13. }  
    int[] a = {3,5,9,7,4,13,15,0,2,20};
    boolean[] b = new boolean[21];
    
    for(int i=0;i<a.length;i++) {
      b[a[i]] = true;
    }
    
    for(int i=0;i<b.length;i++) {
      if(b[i]) {
        System.out.print(i+",");
      }
    
    }
    
    转自:
    http://microjava.javaeye.com/blog/688643
    展开全文
  • #include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;algorithm&gt; using namespace std; //--------------------------------...// 普通排序算法 //---------------------...
    #include <iostream>
    #include <time.h>
    #include <algorithm>
    
    using namespace std;
    
    //---------------------------------------------
    //                   普通排序算法
    //---------------------------------------------
    
    // 插入排序
    void insertSort(int data[], int len)
    {
        int i = 0;
        int j = 0;
        clock_t start, finish;
        double totaltime;
    
        start = clock();
        // 排序
        for(; i<len; i++)
        {
            int tmp = data[i]; // 将当前的元素提取出来
            for(j = i; data[j-1] > tmp && j > 0; j--) // tmp小于前面的元素时进入循环
            {
                data[j] = data[j - 1]; // 将所有大于tmp的元素都向后移动一个位置
            }
            data[j] = tmp;
        }
    
        finish = clock();
        totaltime = (double)(finish - start)/CLOCKS_PER_SEC;
        cout << "插入排序的运行时间:" << totaltime <<  "秒" << endl;
    }
    
    //选择排序
    void selectSort(int data[], int len)
    {
        int i = 0;
        int j = 0;
        int least = 0;
    
        for(; i < len - 1; i++) // 最后一次比较时结果已经出来
        {
            least = i;
            for(j = i + 1; j < len; j++)
            {
                if(data[j] < data[least])
                    least = j;
            }
            swap(data[i], data[least]);
        }
    }
    
    //冒泡排序
    void bubbleSort(int data[], int len)
    {
        for(int i = 0; i < len; i++)
        {
            for(int j = len - 1; j > 0; j--)
            {
                if(data[j] < data[j - 1])
                    swap(data[j], data[j - 1]);
            }
        }
    }
    //---------------------------------------------
    //                   高效排序算法
    //---------------------------------------------
    
    // 希尔排序
    void shellSort(int data[], int len)
    {
        int increment = len/3 + 1;
        while(increment > 0)
        {
            for(int i = increment; i < len; i++)
            {
                //每个增量间隔内,实现插入排序,两个for循环和插入排序一样,只不过第二个for循环里参数略有调整而已,和h有关
                for(int j = i; j < len; j += increment)
                {
                    for(int k = j; (k - increment >= 0) && data[k] < data[k - increment]; k -= increment)
                    {
                        swap(data[k], data[k-increment]);
                    }
                }
            }
            increment = (increment-1) / 3;
        }
    }
    
    // 堆排序
    void moveDown(int data[], int first, int last)
    {
        int largest = 2 * first + 1;
    
        while(largest <= last)
        {
            // first有两个孩子,分别是2*first+1 和2*first+2 并且第二个孩子大于第一个孩子
            if(largest < last && data[largest] < data[largest + 1])
                largest ++;
    
            if(data[first] < data[largest])
            {
                swap(data[first], data[largest]);
                first = largest;
                largest = 2 * first + 1;
            }
            else
            {
                largest = last + 1;
            }
        }
    }
    
    void heapSort(int data[], int len)
    {
        for(int i = len/2 - 1; i >= 0; --i)
        {
            moveDown(data, i, len - 1); // 创建堆
        }
    
        for(int i = len - 1; i >= 1; --i)
        {
            swap(data[0], data[i]);
            moveDown(data, 0, i - 1);   // 重建堆
        }
    }
    
    // 快速排序
    void _quickSort(int data[], int first, int last)
    {
        swap(data[(first + last) / 2], data[first]);
        int bound = data[first];
        int lower = first + 1;
        int upper = last;
    
        while(lower < upper)
        {
            while(data[lower] < bound)        // 寻找大于边界值的值
                lower ++;
            while(data[upper] > bound)        // 寻找小于边界值的值
                upper --;
            if(lower < upper)
            {
                swap(data[lower ++], data[upper --]); // 交换寻找到的两个值
            }
            else
            {
                lower ++;
            }
        }
    
        swap(data[upper], data[first]);      // 将边界值与upper交换,目的是将边界值放在左边数组的最右位置
        if(first < upper - 1)
            _quickSort(data, first, upper - 1);
        if(upper + 1 < last)
            _quickSort(data, upper + 1, last);
    }
    
    void quickSort(int data[], int len)
    {
        if(len < 2)
        {
            return;
        }
        int max = 0;
        int i = 0;
    
        for(; i < len; i++)             // 寻找数组中最大的数
        {
            if(data[i] > data[max])
                max = i;
        }
        swap(data[max], data[len- 1]); //将最大的数放在数组的末尾
        _quickSort(data, 0, len - 2);
    }
    
    // 归并排序
    void mergeSort(int data[], int len)
    {
    
    }
    
    int main()
    {
        int data[14] = {2,1,4,6,99,45,23,5,22,0,13,44,101,100};
        //insertSort(data, 10);
        //selectSort(data, 10);
        //bubbleSort(data, 10);
        //shellSort(data, 14);
        //heapSort(data, 14);
        quickSort(data, 14);
    
        for(int i = 0; i<14; i++)
        {
            cout << data[i] << " ";
        }
        cout << endl;
    
        return 0;
    }
    

     

    展开全文
  • 如标题,这里讨论的是基于比较的排序算法中最高效的三种算法和希尔排序。堆排序、归并排序、快速排序的平均时间复杂度均为O(NlogN)。前面有介绍过O(N2)的三种简单排序算法(见三大简单排序算法——插入、选择、冒泡...

    如标题,这里讨论的是基于比较的排序算法中最高效的三种算法和希尔排序。堆排序、归并排序、快速排序的平均时间复杂度均为O(NlogN)。前面有介绍过O(N2)的三种简单排序算法(见三大简单排序算法——插入、选择、冒泡),其中实际表现最好的要属希尔排序。可以证明通过交换相邻元素来进行排序的任何算法都需要O(N2)的平均时间,其中插入排序虽然不是通过交换来排序,但是可以等价为交换的操作,依然是O(N2)。这里讨论的堆排序、归并排序、快速排序均是平均时间复杂度O(NlogN)的算法,实际表现最好的要属快速排序。可以证明O(NlogN)是基于比较的排序算法的时间复杂度下界。所以这三种排序算法都是渐进最优的。最后介绍一下C++的algorithm库中的sort()函数,一般我们自己写的排序算法优化不够时都是达不到这个效率的。还有会对这些算法在大规模数据下的运行时间进行一个简单的测试。

    排序算法相关知识

    逆序:逆序是指数组中具有性质i>ji>j但是A[i]<A[j]A[i]<A[j]的序偶(A[i],A[j])(A[i],A[j])。(升序排列的情况,反之亦然)

    排序的过程就是消除逆序的过程。很明显逆序的最大数目为N1i=1i=N(N1)2∑i=1N−1i=N(N−1)2,平均情况下逆序数目为最大的一半即N(N1)/4N(N−1)/4

    很容易看出,通过交换相邻元素一次最多只能消除一个逆序。所以通过交换相邻元素来排序的算法的平均时间复杂度一定为O(N2)O(N2)

    而要突破O(N2)O(N2)的时间屏障,就必须在一次交换/操作中消除不止一个逆序。下面的排序算法都有这个特点。

    另外如果下列实现中有要交换元素的均调用如下的模板。

    template<typename T>
    void swap(T & x , T & y)
    {
        T tmp = x;
        x = y;
        y = tmp;
    }

    希尔排序

    希尔排序(Shell sort)是第一批冲破O(N2)O(N2)时间屏障的算法之一。也称缩小增量排序。上一篇(三大简单排序算法——插入、选择、冒泡)介绍得很详细。这里贴出代码。

    //希尔排序,效率惊人
    void Shell_sort(ElemType A[],int n)
    {
        for(int d=n/2; d>0; d/=2)
        {
            for(int i=d; i<n; i++)
            {
                ElemType tmp = A[i];
                int j = i-d;
                while(j >= 0 && tmp < A[j])
                {
                    A[j+d] = A[j];
                    j = j-d;
                }
                A[j+d] = tmp;
            }
        }
    }

    这里的增量序列是n/2,n/4,...,1n/2,n/4,...,1,为最原始的希尔序列。但这并不是高效的增量序列,一个更加高效的增量序列为Hibbard增量,形如1,3,7,...,2k11,3,7,...,2k−1(使用时需要从合适的位置逆序),可以证明Hibbard增量的希尔排序最坏情形时间复杂度为O(N3/2)O(N3/2)。希尔排序的算法实现很简单,但是分析却是很困难的。其实还有更好的增量序列,可以参见 Shellsort - Wikipedia - Gap sequences
    动图演示(以下动图均来自Wikipedia):
    此处输入图片的描述

    堆排序

    heap sort,这个介绍堆时也是介绍的很详细的。见基本数据结构——堆优先队列 & 堆
    实现:

    //升序排列、最大堆 
    void sift_down(ElemType A[],int i,int n)
    {
        ElemType tmp;
        int child;
        for(tmp = A[i]; 2*i <= n; i = child)
        {
            child = 2*i;
            if(child != n && A[child+1] > A[child])
                child ++;
            if(tmp < A[child])
                A[i] = A[child];
            else 
                break; 
        }
        A[i] = tmp;
    }
    //将数组建堆然后排序——升序 
    void heap_sort(ElemType A[],int n)
    {
        for(int i = n/2; i>0; i--)
            sift_down(A,i,n);
        for(int i=n; i>1; i--)
        {
            swap<ElemType>(A[1],A[i]);
            sift_down(A,1,i-1);
        }
    }

    需要注意的是这里堆排序的实现要求给数组多分配一个内存。当然可以将其改为与其他排序一致,这很容易做到,但我个人更偏向于现在这种实现。
    动图演示:
    此处输入图片的描述

    归并排序

    归并排序(Merge sort)采用分治策略。思路也很简单:将数组分为两个等长子数组,对两个子数组递归采用归并排序来排序,然后将两个数组合并,其中递归结束条件为子数组长为1直接返回。则时间T(N)=T(N/2)+NT(N)=T(N/2)+N,由主定理得到时间复杂度为O(NlogN)O(NlogN)

    实现也很清晰很简单。

    void merge_sort(ElemType A[], int n)
    {
        ElemType * TmpArr = new ElemType[n];
        m_sort(A,TmpArr,0,n-1);
        delete [] TmpArr;
    }
    void m_sort(ElemType A[], ElemType TmpArr[], int left, int right)
    {
        if(left < right)
        {
            int center = (left + right) / 2;
            m_sort(A, TmpArr, left, center);
            m_sort(A, TmpArr, center+1, right);
            merge(A, TmpArr, left, center+1, right);
        }
    }
    //两个子数组的合并,lpos~rpos-1 and rpos~rightend ,临时存储在TmpArr[rpos~rightend] 
    void merge(ElemType A[], ElemType TmpArr[], int lpos, int rpos, int rightend)
    {
        int leftend = rpos - 1;
        int tmppos = lpos;
        int begin = lpos;
        while(lpos <= leftend && rpos <= rightend)
        {
            if(A[lpos] <= A[rpos])
                TmpArr[tmppos ++] = A[lpos ++];
            else
                TmpArr[tmppos ++] = A[rpos ++];
            //TmpArr[tmppos++] = A[lpos] <= A[rpos] ? A[lpos ++] : A[rpos ++];
        }
        while(lpos <= leftend)
            TmpArr[tmppos ++] = A[lpos ++];
        while(rpos <= rightend)
            TmpArr[tmppos ++] = A[rpos ++];
        for(int i = begin; i <= rightend; i ++)
            A[i] = TmpArr[i];
    }

    其中动态分配了一个与原数组等长的数组存放那些临时子数组合并之后的数组。这样实现比在每一次递归中都去申请一个数组来存放临时数据要更好。
    动图演示:
    此处输入图片的描述

    快速排序

    Quick sort)最近很烦,写到这真的无心去写了。有空再优化。现在没有优化甚至都比不过希尔排序、堆排序和归并排序。当然差std::sort肯定是差远了。

    给一个算法导论上的实现:

    //划分
    int Partition(int A[], int p, int r)
    {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j<r; j++)
        {
            if (A[j] <= x)
            {
                i++;
                if (i != j)
                    swap(A[i], A[j]);
            }
        }
        swap(A[i + 1], A[r]);
        return i + 1;
    }
    
    //随机化的划分函数,使主元随机化 
    int Randomized_Partition(int A[], int p, int r)
    {
        int i = rand() % (r - p + 1) + p;   //产生p到r的随机数
        swap(A[i], A[r]);
        return Partition(A, p, r);
    }
    
    void Quick_Sort(int A[], int p, int r)
    {
        if (p < r)
        {
            int q = Randomized_Partition(A, p, r);
            Quick_Sort(A, p, q - 1);
            Quick_Sort(A, q + 1, r);
        }
    }
    void quick_sort2(int A[], int n)
    {
        Quick_Sort(A, 0, n - 1);
    }

    动图演示:
    此处输入图片的描述

    排序算法的时间下界

    可以使用决策树模型证明通过比较元素大小实现排序的排序算法的复杂度下界为O(NlogN)。所以快速排序、堆排序、归并排序都是渐进最优的。希尔排序由于增量序列的改变时间界会发生改变,但实际使用效果一般都很理想。并不差前面的三个排序算法多少,某些情况下甚至可能更优一点。

    C++ STL sort()函数

    一般我们自己实现的排序算法在优化不够的情况下都达不到C++的algorithm库中的sort()函数的效率。
    std::sort的实现采用了快速排序、插入排序、堆排序。并且进行了编译优化。一般是比不过的。

    调用方式,可以传入两个参数,或者三个参数。第一个参数为指向初始元素的指针,第二个参数为指向最后一个待排序元素的下一个位置的指针(或者迭代器),第三个元素可选,默认进行升序排序,可以定义一个返回值为bool类型的比较函数。当对结构或者对象进行排序时,重载运算符或者传入一个函数参数都可以实现排序。

    std::sort(A,A+n);    //对数组A中的n个元素排序
    std::sort(A.begin(),A.end(),cmp);   //对容器A中所有元素按照比较函数cmp()的规则进行排序

    简单的时间测试

    我对上述实现以及以前O(N2)的排序算法进行了一个测试。结果如下:

    test 1: 1e5 elements,静态分配
    simple aort algoritms :
    bubble sort time : 15735ms
    selection sort time : 10665ms
    insertion sort time : 1095ms
    binary insertion sort time : 872ms
    
    efficient sort algorithms :
    shell sort time : 13ms
    merge sort time : 15ms
    heap sort time : 8ms
    quick sort time : 9ms
    stl sort function time : 8ms
    
    test 2: 1e7 elements, 动态分配
    efficient sort algorithms :
    shell sort time : 1985ms
    merge sort time : 1858ms
    heap sort time : 1816ms
    quick sort time : 2010ms
    stl sort function time : 697ms

    ps: 测试时请将编译器设置为release模式。不然不开优化std::sort会非常慢。可以看到开启优化之后std::sort是吊打一切的存在。愉快地使用STL吧!

    源码下载。

    参考资料:数据结构与算法分析——C语言描述、算法导论

    展开全文
  • 1.1 希尔排序(Shellsort)的名字源于他的发现者Donald Shell,该算法是冲破二次时间屏障的第一批算法之一。 希尔排序使用一个序列h1,h2,..,ht,叫做增量排序(increment sequence)。只要h1=1,任何增量序列都是可行的。...

    1. 希尔排序


    1.1 希尔排序(ShellSort)的名字源于他的发现者Donald Shell,该算法是冲破二次时间屏障的第一批算法之一。希尔排序使用一个序列h1,h2,..,ht,叫做增量排序(increment sequence)。只要h1=1,任何增量序列都是可行的。一个重要性知识,一个h[k]-排序的数据(后面将是h[k-1]-排序)保持它的h[k]-排序性。h[k]排序的一般做法是,对h[k]个独立的子数组执行一次插入排序


    1.2 增量序列一般认为h1=1 ;h[i+1]=3h[i] +1比较合适


    1.3 希尔排序的核心是利用h个分割位置将数组分为多个子数组。可以根据3个不同的特征改进。

    (1)增量序列

    (2)除最后一次外,其他各次都采用一种简单的排序算法

    (3)仅应用于最后一次(h[1]排序)的简单排序算法


     实现:  

    template<class T>
    void shellSort(T a[], int n)
    {
    	int i, j, k, leap;
    	int increment[20];
    	//Create an appropriate number of increments h
    	for (leap = 1, i = 0; leap < n; i++)
    	{
    		increment[i] = leap;
    		leap = 3 * leap + 1;
    	}
    	//loop on the number of different increments h
    	for (i--; i >= 0; i--)
    	{
    		leap = increment[i];
    		//loop on the subarrays h-sorted 
    		for (j = leap; j < n; j++)
    		{
    			//insertion sort for subarray containing every 
    			if (a[j - leap]>a[j])
    			{
    				T temp = a[j];
    				for (k = j; a[k - leap]>temp&&k >=leap; k -= leap)
    					a[k] = a[k - leap];
    				a[k] = temp;
    			}
    		}
    	}
    
    }


    2. 堆排序 


    2.1 堆是具有以下两个属性的二叉树:

    (1)每个节点的值不会小于其子节点的值

    (2)全是平衡的,最底层的叶子结点都位于最左边的位置上


    实现:

    template<class T>
    void heapSort(T a[], int n)
    {
    	for (int i = n / 2 - 1; i >= 0; --i)	//create the heap
    		moveDown(a, i, n - 1);
    	for (int i = n - 1; i >= 1; --i)
    	{
    		swap(a[0], a[i]);				//move the largest item to a[i]
    		moveDown(a, 0, i - 1);				//restore the heap property
    	}
    
    }
    
    template<class T>
    void moveDown(T a[], int first, int last)
    {
    	int i = 2 * first + 1;
    	
    	while (i < last)
    	{
    	
    		if (i + 1 < last&&			//first has two children(2*first+1 and 2*first+2)
    			a[i] < a[i + 1])		//and the second is larger than the first
    			i++;
    		if (a[i] <= a[first])		//the heap property isn't violated by data[first]
    			break;
    
    		swap(a[first], a[i]);		//if necessary
    		first = i;			//swap child and parent
    		i = 2 * first + 1;		//and move down
    	}
    	
    }



    3. 快速排序 


    3.1 分治策略(divide-and-conquer)

    分:将问题分成一些小的问题然后递归求解

    治:将分的各个阶段解得的各个答案修补到一起


    实现:

    template<class T>
    void quickSort(T a[], int l,int r)
    {
    	if (l < r)
    	{
    		swap(a[l], a[(l + r) / 2]);
    		int i = l, j = r;
    		T x = a[i];
    		while (i < j)
    		{
    			while (i < j&&a[j] > x)		// 从右向左找第一个小于x的数 
    				j--;
    			if (i < j)
    				a[i++] = a[j];
    			while (i < j&&a[i] < x)		// 从左向右找第一个大于等于x的数  
    				i++;
    			if (i < j)
    				a[j--] = a[i];
    		}
    		a[i] = x;
    		quickSort(a, l, i - 1);			//递归调用
    		quickSort(a, i + 1, r);
    	}
    }
    



    4. 归并排序 


    4.1 归并排序的主要过程是将多个已经排好序的子数组合并成一个排好序的数组。然而,这个子数组必须先排好序,具体方法是合并更小的、已排好序的子数组。当子数组的元素少于两个时,将数组一分为二的过程就会停止。这个算法本身也是递归的。


    实现:

    template<class T>
    void Merge(T a[], int first, int mid, int last, T temp[])
    {
    	int i = first, j = mid + 1;
    	int m = mid, n = last;
    	int k = 0;
    	while (i <= m&&j <= n)
    	{
    		if (a[i] <= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    	while (i <= m)
    		temp[k++] = a[i++];
    	while (j <= n)
    		temp[k++] = a[j++];
    
    	for (i = 0; i < k; i++)
    		a[first + i] = temp[i];
    }
    template<class T>
    void mSort(T a[], int first, int last, int temp[])
    {
    	if (first < last)
    	{
    		int mid = (first + last) / 2;
    		mSort(a, first, mid, temp);		//左边有序
    		mSort(a, mid + 1, last, temp);	<span style="white-space:pre">	</span>//右边有序
    		Merge(a, first, mid, last, temp);	//将两个合并
    	}
    }
    template<class T>
    bool mergeSort(T a[], int n)
    {
    	T *p = new T[n];
    	if (p == nullptr)
    		return false;
    	mSort(a, 0, n - 1, p);
    	delete[]p;
    	return true;
    }
    


    展开全文
  • 在前面文章中介绍的直接插入排序,它对于已经基本有序的数据进行排序,效率会很高,而如果对于最初的数据是倒序排列的,则每次比较都需要移动数据,导致算法效率降低。 希尔排序的基本思想就是:将需要排序的序列...
  • Timsort——自适应、稳定、高效排序算法

    万次阅读 多人点赞 2018-10-08 22:10:12
    Timsort是一种混合、稳定高效排序算法,源自合并排序和插入排序,旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列,并使用该知识更有效...
  • 高效排序算法

    千次阅读 2018-05-13 16:28:26
    特点:高效,时间复杂度为nlogn。采用分治法的思想:首先设置一个轴值pivot,然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分,接下来对划分完的子序列进行快排直到子序列为一个元素为止。...
  • **跪求求高效排序算法???**问题描述 给出n个数,找出这n个数的最大值,最小值,和。输入格式 第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式 输出三行,每行一个...
  • Shell排序算法思想是:先将这个待排记录序列分割成为若干子序列(子数组)分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。 说明:对每个“增量”h进行一次排序成为...
  • public static void quickSort(int start, int end) { int x = data[start]; int pLeft = start, pRight = end;// 以第一个数为参照做比较 if (pLeft >= pRight){ return;...while (pLeft =
  • ){ //针对每个步长的每一项,采用插入排序  int tmp=data[j];  k=j;  while(k-step>=0&&tmp[k-step]){  data[k]=data[k-step];  k-=step;  }  data[k]=tmp;  j+=...
  • 2、算法的伪代码和排序方法如下所示(其中方法是实现对整数的排序方式)。 // 基数排序的伪代码 // RadixSort() // for d = 1 to 最长数字的最左边数字所在的位置 // 根据第d位数字将所有的数字分别分配到堆0至堆9中...
  • 2、归并排序的设计思想:是将一个数组的两个有序的部分合并成一个有序数组,其算法的本质也是依靠递归来实现的。 3、归并排序的缺陷:在于需要额外的存储空间来合并数组。在归并排序的过程中必须使用一个临时数组,...
  • 排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。 在处理堆排序时面临两个问题:一个...具体过程见算法分析及注释。 //堆排序的伪代码 //heapsort(data[]) // data转变成一个堆; // for i =
  • 提到排序算法,我们的第一反可能是冒泡排序、插入排序、快速排序、归并等经典排序算法。推荐一篇很棒的博客,里面列举比较了10大排序算法(附有很棒的动图),这里就不多说了。 Chrome浏览器引擎v8使用的则是不属于...
  • 快速排序时对冒泡排序的一种改进。 实现思想:通过一趟排序将待排序记录(数组)分割成独立的两部分,其中一部分的元素均比另一部分的元素要小,则可以对这两部分记录继续进行排序,从而达到整个序列有序。实现的...
  • 目录序言介绍[^1]原理补充内容分治法介绍[^3]递归介绍[^4]快速排序算法基本思想基准数字的选取利用i,j作为指针对数组进行检索和排序在C语言为例子实现快速排序算法总结 序言 笔者还只是大一新生,在做我们学校OJ平台...
  • 已知最大数是20,把数据从小到大排序,而且算法复杂度只能是1,不能用Java提供的类实现,如Arrays.sort()等。 思路: 最大是20,就用一个长度21的boolean数组,把数作为index标记出现过的。然后从小到大...
  • 通过位操作或数组操作,一次扫描,一次赋值即可完成,对于数据量巨大,数据范围较小的... * @brief 对所有元素都为正整数的数组进行排序 * @defgroup sort * @{ */ #include &lt;stdio.h&gt; /...

空空如也

空空如也

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

高效排序算法