精华内容
下载资源
问答
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...

    阅读此文推荐:前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。

    概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    我们这里说说八大排序就是内部排序。

        

        当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


     

    1.插入排序—直接插入排序(Straight Insertion Sort)


    基本思想:

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    直接插入排序示例:

     

    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    算法的实现:

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    
    
    void InsertSort(int a[], int n)
    {
    	for(int i= 1; i<n; i++){
    		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j= i-1;	
    			int x = a[i];		 //复制为哨兵,即存储待排序元素
    			a[i] = a[i-1];           //先后移一个元素
    			while(x < a[j]){	 //查找在有序表的插入位置
    				a[j+1] = a[j];
    				j--;		 //元素后移
    			}
    			a[j+1] = x;		 //插入到正确位置
    		}
    		print(a,n,i);			//打印每趟排序的结果
    	}
    	
    }
    
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	InsertSort(a,8);
    	print(a,8,8);
    }
    

     

    效率:

     

    时间复杂度:O(n^2).

    其他的插入排序有二分插入排序,2-路插入排序。

     

     2. 插入排序—希尔排序(Shell`s Sort)


    希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

    基本思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    操作方法:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    希尔排序的示例:shell排序的排序过程

    假设待排序文件有10个记录,其关键字分别是:49,38,65,97,76,13,27,49,55,04。

    增量系列的取值依次为:5,3,1

     

    算法实现:

    我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

    即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    /**
     * 直接插入排序的一般形式
     *
     * @param int dk 缩小增量,如果是直接插入排序,dk=1
     *
     */
    
    void ShellInsertSort(int a[], int n, int dk)
    {
    	for(int i= dk; i<n; ++i){
    		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j = i-dk;	
    			int x = a[i];			//复制为哨兵,即存储待排序元素
    			a[i] = a[i-dk];			//首先后移一个元素
    			while(x < a[j]){		//查找在有序表的插入位置
    				a[j+dk] = a[j];
    				j -= dk;			 //元素后移
    			}
    			a[j+dk] = x;			//插入到正确位置
    		}
    		print(a, n,i );
    	}
    	
    }
    
    /**
     * 先按增量d(n/2,n为要排序数的个数进行希尔排序
     *
     */
    void shellSort(int a[], int n){
    
    	int dk = n/2;
    	while( dk >= 1  ){
    		ShellInsertSort(a, n, dk);
    		dk = dk/2;
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	//ShellInsertSort(a,8,1); //直接插入排序
    	shellSort(a,8);			  //希尔插入排序
    	print(a,8,8);
    }
    

     

    希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

     

    3. 选择排序—简单选择排序(Simple Selection Sort)


    基本思想:

    在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

    简单选择排序的示例:

     

    操作方法:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。

     

    算法实现:

    void print(int a[], int n ,int i){
    	cout<<"第"<<i+1 <<"趟 : ";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    /**
     * 数组的最小值
     *
     * @return int 数组的键值
     */
    int SelectMinKey(int a[], int n, int i)
    {
    	int k = i;
    	for(int j=i+1 ;j< n; ++j) {
    		if(a[k] > a[j]) k = j;
    	}
    	return k;
    }
    
    /**
     * 选择排序
     *
     */
    void selectSort(int a[], int n){
    	int key, tmp;
    	for(int i = 0; i< n; ++i) {
    		key = SelectMinKey(a, n,i);           //选择最小的元素
    		if(key != i){
    			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
    		}
    		print(a,  n , i);
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	cout<<"初始值:";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl<<endl;
    	selectSort(a, 8);
    	print(a,8,8);
    }
    

     

     简单选择排序的改进——二元选择排序

     

    简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。具体实现如下:

    /** 这是伪函数, 逻辑判断不严谨
    void selectSort(int r[],int n) {
    	int i ,j , min ,max, tmp;
    	for (i=1 ;i <= n/2;i++) {  
    		// 做不超过n/2趟选择排序 
    		min = i; max = i ; //分别记录最大和最小关键字记录位置
    		for (j= i+1; j<= n-i; j++) {
    			if (r[j] > r[max]) { 
    				max = j ; continue ; 
    			}  
    			if (r[j]< r[min]) { 
    				min = j ; 
    			}   
    	  }  
    	  //该交换操作还可分情况讨论以提高效率
    	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
    	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
     
    	} 
    }
     */
    void selectSort(int a[],int len) {
            int i,j,min,max,tmp;  
            for(i=0; i<len/2; i++){  // 做不超过n/2趟选择排序 
                min = max = i;  
                for(j=i+1; j<=len-1-i; j++){  
    				//分别记录最大和最小关键字记录位置
                    if(a[j] > a[max]){  
                        max = j;  
                        continue;  
                    }  
                    if(a[j] < a[min]){  
                        min = j;  
                    }  
                }  
    			//该交换操作还可分情况讨论以提高效率
                if(min != i){//当第一个为min值,不用交换  
                    tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
                }  
                if(min == len-1-i && max == i)//当第一个为max值,同时最后一个为min值,不再需要下面操作  
                    continue;  
                if(max == i)//当第一个为max值,则交换后min的位置为max值  
                    max = min;  
                if(max != len-1-i){//当最后一个为max值,不用交换  
                    tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
                }
    			print(a,len, i);			
            }  
     }

     

    4. 选择排序—堆排序(Heap Sort)


    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)

    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:


    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)


                                 

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    
    
    /**
     * 已知H[s…m]除了H[s] 外均满足堆的定义
     * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
     *
     * @param H是待调整的堆数组
     * @param s是待调整的数组元素的位置
     * @param length是数组的长度
     *
     */
    void HeapAdjust(int H[],int s, int length)
    {
    	int tmp  = H[s];
    	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
        while (child < length) {
    		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
    			++child ;
    		}
    		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
    			H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点
    			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
    			child = 2*s+1;
    		}  else {			 // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
    			 break;
    		}
    		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
    	}
    	print(H,length);
    }
    
    
    /**
     * 初始堆进行调整
     * 将H[0..length-1]建成堆
     * 调整完之后第一个元素是序列的最小的元素
     */
    void BuildingHeap(int H[], int length)
    { 
    	//最后一个有孩子的节点的位置 i=  (length -1) / 2
    	for (int i = (length -1) / 2 ; i >= 0; --i)
    		HeapAdjust(H,i,length);
    }
    /**
     * 堆排序算法
     */
    void HeapSort(int H[],int length)
    {
        //初始堆
    	BuildingHeap(H, length);
    	//从最后一个元素开始对序列进行调整
    	for (int i = length - 1; i > 0; --i)
    	{
    		//交换堆顶元素H[0]和堆中最后一个元素
    		int temp = H[i]; H[i] = H[0]; H[0] = temp;
    		//每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整
    		HeapAdjust(H,0,i);
      }
    } 
    
    int main(){
    	int H[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(H,10);
    	HeapSort(H,10);
    	//selectSort(a, 8);
    	cout<<"结果:";
    	print(H,10);
    
    }
    
    

     

    分析:

    设树深度为k,。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式: 

                                   

    而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。

     

    5. 交换排序—冒泡排序(Bubble Sort)


    基本思想:

    在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

    冒泡排序的示例:

     

    算法的实现:

    void bubbleSort(int a[], int n){
    	for(int i =0 ; i< n-1; ++i) {
    		for(int j = 0; j < n-i-1; ++j) {
    			if(a[j] > a[j+1])
    			{
    				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
    			}
    		}
    	}
    }

     

    冒泡排序算法的改进

    对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    void Bubble_1 ( int r[], int n) {
    	int i= n -1;  //初始时,最后位置保持不变
    	while ( i> 0) { 
    		int pos= 0; //每趟开始时,无记录交换
    		for (int j= 0; j< i; j++)
    			if (r[j]> r[j+1]) {
    				pos= j; //记录交换的位置 
    				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		i= pos; //为下一趟排序作准备
    	 } 
    }  
    

     

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    改进后的算法实现为:

    void Bubble_2 ( int r[], int n){
    	int low = 0; 
    	int high= n -1; //设置变量的初始值
    	int tmp,j;
    	while (low < high) {
    		for (j= low; j< high; ++j) //正向冒泡,找到最大者
    			if (r[j]> r[j+1]) {
    				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		--high;					//修改high值, 前移一位
    		for ( j=high; j>low; --j) //反向冒泡,找到最小者
    			if (r[j]<r[j-1]) {
    				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
    			}
    		++low;					//修改low值,后移一位
    	} 
    } 

     

    6. 交换排序—快速排序(Quick Sort)


    基本思想:

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程

    算法的实现:

     递归实现:

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];								//基准元素
    	while(low < high){								    //从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void quickSort(int a[], int low, int high){
    	if(low < high){
    		int privotLoc = partition(a,  low,  high);  //将表一分为二
    		quickSort(a,  low,  privotLoc -1);			//递归对低子表递归排序
    		quickSort(a,   privotLoc + 1, high);		//递归对高子表递归排序
    	}
    }
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,0,9);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    分析:

    快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。


    快速排序的改进

    在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下:

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];					//基准元素
    	while(low < high){					//从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void qsort_improve(int r[ ],int low,int high, int k){
    	if( high -low > k ) { //长度大于k时递归, k为指定的数
    		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
    		qsort_improve(r, low, pivot - 1,k);
    		qsort_improve(r, pivot + 1, high,k);
    	} 
    } 
    void quickSort(int r[], int n, int k){
    	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序
    
    	//再用插入排序对基本有序序列排序
    	for(int i=1; i<=n;i ++){
    		int tmp = r[i]; 
    		int j=i-1;
    		while(tmp < r[j]){
    			r[j+1]=r[j]; j=j-1; 
    		}
    		r[j+1] = tmp;
    	} 
    
    } 
    
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,9,4);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    7. 归并排序(Merge Sort)


    基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    归并排序示例:

     

     

    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵
    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
    5. 合并结束。
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    }

     

    归并的迭代算法

    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    	print(rf,n+1);
    }
    
    void MergeSort(ElemType *r, ElemType *rf, int lenght)
    { 
    	int len = 1;
    	ElemType *q = r ;
    	ElemType *tmp ;
    	while(len < lenght) {
    		int s = len;
    		len = 2 * s ;
    		int i = 0;
    		while(i+ len <lenght){
    			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
    			i = i+ len;
    		}
    		if(i + s < lenght){
    			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
    		}
    		tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
    	}
    }
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	int b[10];
    	MergeSort(a, b, 10);
    	print(b,10);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    两路归并的递归算法

    void MSort(ElemType *r, ElemType *rf,int s, int t)
    { 
    	ElemType *rf2;
    	if(s==t) r[s] = rf[s];
    	else
    	{ 
    		int m=(s+t)/2;			/*平分*p 表*/
    		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
    		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
    		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
    	}
    }
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
    {   /*对顺序表*p 作归并排序*/
    	MSort(r, rf,0, n-1);
    }

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。

     

    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                  

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

     

    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    算法实现:

    Void RadixSort(Node L[],length,maxradix)
    {
       int m,n,k,lsp;
       k=1;m=1;
       int temp[10][length-1];
       Empty(temp); //清空临时空间
       while(k<maxradix) //遍历所有关键字
       {
         for(int i=0;i<length;i++) //分配过程
        {
           if(L[i]<m)
              Temp[0][n]=L[i];
           else
              Lsp=(L[i]/m)%10; //确定关键字
           Temp[lsp][n]=L[i];
           n++;
       }
       CollectElement(L,Temp); //收集
       n=0;
       m=m*10;
      k++;
     }
    }

     

     

     

    总结


    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:

     

                                 时间复杂度函数O(n)的增长情况

    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

     

    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。
      2、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

     

    注明:转载请提示出处:http://blog.csdn.net/hguisu/article/details/7776068

     

     

     

    感谢您的支持,我会继续努力的! 扫码打赏,你说多少就多少

             

    展开全文
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...

    一、什么是排序算法

    1.1、排序定义

    对一序列对象根据某个关键字进行排序。

    1.2、排序术语

    稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
    不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
    内排序:所有排序操作都在内存中完成;
    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度运行完一个程序所需内存的大小。

    1.3、算法总结

    (注意:n指数据规模;k指“桶”的个数;In-place指占用常数内存,不占用额外内存;Out-place指占用额外内存

    1.4、算法分类

    1.5、比较和非比较的区别

    常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

    二、冒泡排序(Bubble Sort)

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 

    2.1、算法描述

    • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    • 针对所有的元素重复以上的步骤,除了最后一个;
    • 重复步骤1~3,直到排序完成。

    2.2、动图演示

    2.3、代码实现

    /**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++)
    		for (int j = 0; j < array.length - 1 - i; j++)
    			if (array[j + 1] < array[j]) {
    				int temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    	return array;
    }

    2.4、算法分析

    最佳情况:T(n) = O(n)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    三、选择排序(Selection Sort)

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 

    3.1、算法描述

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

    • 初始状态:无序区为R[1..n],有序区为空;
    • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
    • n-1趟结束,数组有序化了。

    3.2、动图演示

    3.3、代码实现

    /**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++) {
    		int minIndex = i;
    		for (int j = i; j < array.length; j++) {
    			if (array[j] < array[minIndex]) //找到最小的数
    				minIndex = j; //将最小数的索引保存
    		}
    		int temp = array[minIndex];
    		array[minIndex] = array[i];
    		array[i] = temp;
    	}
    	return array;
    }

    3.4、算法分析

    最佳情况:T(n) = O(n2)  最差情况:T(n) = O(n2)  平均情况:T(n) = O(n2)

    四、插入排序(Insertion Sort)

    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

    4.1、算法描述

    一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

    • 从第一个元素开始,该元素可以认为已经被排序;
    • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
    • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
    • 将新元素插入到该位置后;
    • 重复步骤2~5。

    4.2、动图演示

    4.3、代码实现

    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	int current;
    	for (int i = 0; i < array.length - 1; i++) {
    		current = array[i + 1];
    		int preIndex = i;
    		while (preIndex >= 0 && current < array[preIndex]) {
    			array[preIndex + 1] = array[preIndex];
    			preIndex--;
    		}
    		array[preIndex + 1] = current;
    	}
    	return array;
    }

    4.4、算法分析

    最佳情况:T(n) = O(n)   最坏情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    五、希尔排序(Shell Sort)

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    5.1、算法描述

    我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

    • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    • 按增量序列个数k,对序列进行k 趟排序;
    • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    5.2、过程演示

    5.3、代码实现

    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] ShellSort(int[] array) {
    	int len = array.length;
    	int temp, gap = len / 2;
    	while (gap > 0) {
    		for (int i = gap; i < len; i++) {
    			temp = array[i];
    			int preIndex = i - gap;
    			while (preIndex >= 0 && array[preIndex] > temp) {
    				array[preIndex + gap] = array[preIndex];
    				preIndex -= gap;
    			}
    			array[preIndex + gap] = temp;
    		}
    		gap /= 2;
    	}
    	return array;
    }

    5.4、算法分析

    最佳情况:T(n) = O(nlog2 n)  最坏情况:T(n) = O(nlog2 n)  平均情况:T(n) =O(nlog2n) 

    六、归并排序(Merge Sort)

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 

    6.1、算法描述

    • 把长度为n的输入序列分成两个长度为n/2的子序列;
    • 对这两个子序列分别采用归并排序;
    • 将两个排序好的子序列合并成一个最终的排序序列。

    6.2、动图演示

    6.3、代码实现

    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
    	if (array.length < 2) return array;
    	int mid = array.length / 2;
    	int[] left = Arrays.copyOfRange(array, 0, mid);
    	int[] right = Arrays.copyOfRange(array, mid, array.length);
    	return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
    	int[] result = new int[left.length + right.length];
    	for (int index = 0, i = 0, j = 0; index < result.length; index++) {
    		if (i >= left.length)
    			result[index] = right[j++];
    		else if (j >= right.length)
    			result[index] = left[i++];
    		else if (left[i] > right[j])
    			result[index] = right[j++];
    		else
    			result[index] = left[i++];
    	}
    	return result;
    }

    6.4、算法分析

    最佳情况:T(n) = O(n)  最差情况:T(n) = O(nlogn)  平均情况:T(n) = O(nlogn)

    七、快速排序(Quick Sort)

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    7.1、算法描述

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    7.2、动图演示

    7.3、代码实现

    /**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
    	if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
    	int smallIndex = partition(array, start, end);
    	if (smallIndex > start)
    		QuickSort(array, start, smallIndex - 1);
    	if (smallIndex < end)
    		QuickSort(array, smallIndex + 1, end);
    	return array;
    }
    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
    	int pivot = (int) (start + Math.random() * (end - start + 1));
    	int smallIndex = start - 1;
    	swap(array, pivot, end);
    	for (int i = start; i <= end; i++)
    		if (array[i] <= array[end]) {
    			smallIndex++;
    			if (i > smallIndex)
    				swap(array, i, smallIndex);
    		}
    	return smallIndex;
    }
    
    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
    	int temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    }

     


    wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==7.4、算法分析

    最佳情况:T(n) = O(nlogn)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(nlogn) 

    八、堆排序(Heap Sort)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    8.1、算法描述

    • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
    • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
    • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

    8.2、动图演示

     

    8.3、代码实现

    //声明全局变量,用于记录数组array的长度;
    static int len;
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
    	len = array.length;
    	if (len < 1) return array;
    	//1.构建一个最大堆
    	buildMaxHeap(array);
    	//2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
    	while (len > 0) {
    		swap(array, 0, len - 1);
    		len--;
    		adjustHeap(array, 0);
    	}
    	return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
    	//从最后一个非叶子节点开始向上构造最大堆
    	for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1) 
    		adjustHeap(array, i);
    	}
    }
    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
    	int maxIndex = i;
    	//如果有左子树,且左子树大于父节点,则将最大指针指向左子树
    	if (i * 2 < len && array[i * 2] > array[maxIndex])
    		maxIndex = i * 2;
    	//如果有右子树,且右子树大于父节点,则将最大指针指向右子树
    	if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
    		maxIndex = i * 2 + 1;
    	//如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
    	if (maxIndex != i) {
    		swap(array, maxIndex, i);
    		adjustHeap(array, maxIndex);
    	}
    }

    8.4、算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

    九、计数排序(Counting Sort)

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

    9.1、算法描述

    • 找出待排序的数组中最大和最小的元素;
    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

    9.2、动图演示

    9.3、代码实现

    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] CountingSort(int[] array) {
    	if (array.length == 0) return array;
    	int bias, min = array[0], max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		if (array[i] > max)
    			max = array[i];
    		if (array[i] < min)
    			min = array[i];
    	}
    	bias = 0 - min;
    	int[] bucket = new int[max - min + 1];
    	Arrays.fill(bucket, 0);
    	for (int i = 0; i < array.length; i++) {
    		bucket[array[i] + bias]++;
    	}
    	int index = 0, i = 0;
    	while (index < array.length) {
    		if (bucket[i] != 0) {
    			array[index] = i - bias;
    			bucket[i]--;
    			index++;
    		} else
    			i++;
    	}
    	return array;
    }

    9.4、算法分析

    当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。最佳情况:T(n) = O(n+k)  最差情况:T(n) = O(n+k)  平均情况:T(n) = O(n+k)

    十、桶排序(Bucket Sort)

    桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

    10.1、算法描述

    • 人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
    • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
    • 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
    • 从不是空的桶里把排好序的数据拼接起来。 

    注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。

    10.2、图片演示

    10.3、代码实现

    /**
     * 桶排序
     * 
     * @param array
     * @param bucketSize
     * @return
     */
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
    	if (array == null || array.size() < 2)
    		return array;
    	int max = array.get(0), min = array.get(0);
    	// 找到最大值最小值
    	for (int i = 0; i < array.size(); i++) {
    		if (array.get(i) > max)
    			max = array.get(i);
    		if (array.get(i) < min)
    			min = array.get(i);
    	}
    	int bucketCount = (max - min) / bucketSize + 1;
    	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
    	ArrayList<Integer> resultArr = new ArrayList<>();
    	for (int i = 0; i < bucketCount; i++) {
    		bucketArr.add(new ArrayList<Integer>());
    	}
    	for (int i = 0; i < array.size(); i++) {
    		bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
    	}
    	for (int i = 0; i < bucketCount; i++) {
    		if (bucketSize == 1) { // 如果带排序数组中有重复数字时  感谢 @见风任然是风 朋友指出错误
    			for (int j = 0; j < bucketArr.get(i).size(); j++)
    				resultArr.add(bucketArr.get(i).get(j));
    		} else {
    			if (bucketCount == 1)
    				bucketSize--;
    			ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
    			for (int j = 0; j < temp.size(); j++)
    				resultArr.add(temp.get(j));
    		}
    	}
    	return resultArr;
    }

    10.4、算法分析

    桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k)   最差情况:T(n) = O(n+k)   平均情况:T(n) = O(n2)  

    十一、基数排序(Radix Sort)

    基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    11.1、算法描述

    • 取得数组中的最大数,并取得位数;
    • arr为原始数组,从最低位开始取每个位组成radix数组;
    • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

    11.2、动图演示

    11.3、代码实现

    /**
     * 基数排序
     * @param array
     * @return
     */
    public static int[] RadixSort(int[] array) {
    	if (array == null || array.length < 2)
    		return array;
    	// 1.先算出最大数的位数;
    	int max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		max = Math.max(max, array[i]);
    	}
    	int maxDigit = 0;
    	while (max != 0) {
    		max /= 10;
    		maxDigit++;
    	}
    	int mod = 10, div = 1;
    	ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    	for (int i = 0; i < 10; i++)
    		bucketList.add(new ArrayList<Integer>());
    	for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
    		for (int j = 0; j < array.length; j++) {
    			int num = (array[j] % mod) / div;
    			bucketList.get(num).add(array[j]);
    		}
    		int index = 0;
    		for (int j = 0; j < bucketList.size(); j++) {
    			for (int k = 0; k < bucketList.get(j).size(); k++)
    				array[index++] = bucketList.get(j).get(k);
    			bucketList.get(j).clear();
    		}
    	}
    	return array;
    }

    11.4、算法分析

    最佳情况:T(n) = O(n * k)   最差情况:T(n) = O(n * k)   平均情况:T(n) = O(n * k)。基数排序有两种方法:MSD 从高位开始进行排序 LSD 从低位开始进行排序 。基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    • 基数排序:根据键值的每位数字来分配桶
    • 计数排序:每个桶只存储单一键值
    • 桶排序:每个桶存储一定范围的数值
    展开全文
  • :现有的搜索引擎排序算法大多根据网页之间的链接关系进行排序,没有考虑原创和转载文章之间的优先次序。该文提出一种适用于专业搜索引擎的新型排序算法,在排序时优先考虑原创文章,使原创文章的搜索排名得以提高,...
  • 低位优先排序 高位优先排序

    低位优先排序

    长度相同的字符串,由后往前根据字符对字符串分组

    排序前:[1she2, 2sel3, 3seat, 1by2e, 3the2, 5she2, 4she7, 2sel1, 4are2, 2sur3]
    排序后:[1by2e, 1she2, 2sel1, 2sel3, 2sur3, 3seat, 3the2, 4are2, 4she7, 5she2]

    高位优先排序

    长度不同的字符串,由前往后根据字符对字符串分组,递归对子字符串分组
    排序前:[she, sells, the, hantao, daneng, dou, she, like, li, min, doudou, a, banana]
    排序后:[a, banana, daneng, dou, doudou, hantao, li, like, min, sells, she, she, the]

    import java.util.Arrays;
    /**
     * 字符串排序
     * 1、低位优先(只能排序长度相同的字符串)
     * 2、高位优先(要特别注意到达字符串末尾的情况:将已经检查到末尾的字符串所在的子数组排在所有子数组的前面)
     * @author Administrator
     *
     */
    public class sortString {
    
        private static int R = 256; //基于扩展的ASCII字符集
        private static String[] tempArray;//临时数组
    
        //低位优先(只能排序长度相同的字符串)
        private void lowPriorSortString(String[] sameLenString)
        {
            int numArray = sameLenString.length;//字符串数量
            tempArray = new String[numArray];//临时数组
    
            for( int i=sameLenString[0].length()-1;i>=0;i-- )//从低位开始根据每个字符排序
            {
                int[] count = new int[R+1];
                //根据相同字符计数
                for( int j=0;j<numArray;j++ )
                {
                    count[sameLenString[j].charAt(i)+1]++;
                }
                //将频率换成索引
                for( int j=0;j<R;j++ )
                {
                    count[j+1] += count[j];
                }
                //将元素分类
                for( int j=0;j<numArray;j++ )
                {
                    tempArray[count[sameLenString[j].charAt(i)]++] = sameLenString[j];
                }
                //回写
                for( int j=0;j<numArray;j++ )
                {
                    sameLenString[j] = tempArray[j];
                }
            }
        }
    
        //高位优先
        private void highPriorSortString(String[] differentLenString)
        {
            int numArray = differentLenString.length;//字符串数量
            tempArray = new String[numArray];//临时数组
            sort( differentLenString,0,numArray-1,0 );
        }
        //若字符串已结束则返回-1
        private int charAt( String s,int d )
        {
            if( d<s.length() )
            {
                return s.charAt(d);
            }
            else
            {
                return -1;
            }
        }
        //高位优先递归排序
        private void sort( String[] differentLenString,int lo,int hi,int d )
        {
            if( hi<=lo ) return;  //递归出口
            int[] count = new int[R+2];
            //根据相同字符计数
            for( int j=lo;j<=hi;j++ )
            {
                count[charAt( differentLenString[j],d )+2]++;
            }
            //将频率换成索引
            for( int j=0;j<R+1;j++ )
            {
                count[j+1] += count[j];
            }
            //将元素分类
            for( int j=lo;j<=hi;j++ )
            {
                tempArray[count[charAt( differentLenString[j],d )+1]++] = differentLenString[j];
            }
            //回写
            for( int j=lo;j<=hi;j++ )
            {
                differentLenString[j] = tempArray[j-lo];
            }
            //递归的以每个字符串为键进行排序
            for( int j=0;j<R;j++ )
            {
                sort( differentLenString,lo+count[j],lo+count[j+1]-1,d+1 );
            }
        }
    
        public static void main(String[] args) 
        {
            sortString ss = new sortString();
            String[] sameLenString = 
            {   //相同长度的字符串
                "1she2",    
                "2sel3",    
                "3seat",    
                "1by2e",    
                "3the2",    
                "5she2",    
                "4she7",    
                "2sel1",    
                "4are2",    
                "2sur3"
            };
            String[] differentLenString = 
            {   //不同长度的字符串
                    "she",  
                    "sells",
                    "the",
                    "hantao",
                    "daneng",
                    "dou",
                    "she",
                    "like",
                    "li",
                    "min",
                    "doudou",
                    "a",
                    "banana"
            };
            System.out.println("等长字符串排序前:"+Arrays.toString(sameLenString));
            ss.lowPriorSortString(sameLenString);//低位优先(只能排序长度相同的字符串)
            System.out.println("    低位优先排序后:"+Arrays.toString(sameLenString));
            System.out.println("\r\n    非等长字符串:"+Arrays.toString(differentLenString));
            ss.highPriorSortString(differentLenString);//低位优先(只能排序长度相同的字符串)
            System.out.println("高位优先排序后:"+Arrays.toString(differentLenString));
        }
    
    }
    展开全文
  • 排序算法08:优先队列与堆排序

    千次阅读 2017-05-03 23:56:38
    这也是《算法》第四版上讲解堆排序的大致章节结构。另外,本文所有的图都来自于此书。优先队列  普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出...

      堆排序一种是基于二叉堆的排序。本文将从优先队列讲起,循序渐进的实现堆排序。这也是《算法》第四版上讲解堆排序的大致章节结构。另外,本文所有的图都来自于此书。

    优先队列

      普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构,比如每次取值都取最大的元素。

      优先队列有两个核心方法,一个是insert(val)向队列中添加元素,另外一个是delMax()删除最大元素(优先级最高的)并返回。可以考虑使用数组来存储优先队列的数据。

    优先队列有如下三种实现方式:

    1. 有序数组(调用insert方法时使用类似插入排序把新增元素放到正确位置,调用delMax方法时直接取数组最后一个元素,因为此时元素已经是有序状态)
    2. 无序数组(调用insert方法时直接把元素放到数组中,调用dexMax方法时使用类似选择排序的方法从数组中找出最大元素,删除并返回)

    优先队列时间复杂度对比与演示

    堆的算法

      优先队列可以使用一棵堆有序的二叉树来解决。什么叫做堆有序呢?当一棵二叉树的每个几点都大于它的两个子节点时,它被称为堆有序。那么,根节点就是堆有序的二叉树中的最大节点。

      二叉堆可以使用数组来存储。为了方便起见,根节点放在位置1处(位置0不使用),它的两个子节点分别放在位置2和位置3。同理可知,在一个堆中,位置k的节点的父节点的位置为k/2,而它的两个子节点的位置则分别为2k和2k+1.我们就可以这样在树的上下移动:访问a[k]节点的上一层就令k等于k/2,向下一层就令k等于2k或2k+1.

    如下图所示:

    堆的表示

      使用二叉堆,我们就能实现对数级别的插入元素和删除最大元素。

    由下自上的堆有序化(上浮)

      当调用优先队列的insert方法时,我们首先把元素放置到数组的结尾,然后再把该元素上浮到正确的节点,最终形成堆有序状态。

    代码如下:

        //下标为k的元素上浮到正确位置
        function swim(arr,k) {
            while(k>1 && less(arr,parseInt(k/2),k)){
                //父节点索引
                var parentNode = parseInt(k/2);
                exch(arr,parentNode,k);
                k = parentNode;
            }
        }

    由上至下的堆有序化(下沉)

      当调用优先队列的delMax方法时,我们下标为1的元素(最大元素)和数组最后一个元素交换,返回最大元素,数组长度减去1,即删除最后一个元素。此时的位置1元素不一定是最大元素,就需要下沉到正确位置,重新构造有序堆。

    代码如下:

        //下标为k的元素下沉到正确位置
        function sink(arr,k,len) {
            var len = len ||arr.length;
            while(2*k <= len){
                var j = 2*k;
                if(j<len && less(arr,j,j+1)) j++;
                if(!less(arr,k,j)) break;
                exch(arr,k,j);
                k = j;
            }
        }

    堆有序化示例图:

    堆有序化

    堆的操作示例图:

    堆的操作

    优先队列实现

      理解了实现堆有序的上浮和下沉两种方法,优先队列的实现就轻而易举了,代码如下:

        /**
         * 优先队列
         * @constructor
         */
        function MaxQueue() {
            this.queue = [];                //- 存储基于堆的完全二叉树
            this.len   = 0;                 //- 存储于queue[1..len]中,queue[0]未使用
        }
    
        /**
         * 向优先队列中插入元素
         * @param val
         */
        MaxQueue.prototype.insert = function (val) {
            this.queue[++this.len] = val;    //- 从索引1开始添加元素
            //使新增元素上浮到树的正确位置
            swim(this.queue,this.len);
        };
    
        /**
         * 删除优先队列中的最大元素,并返回该元素
         * @returns {*}
         */
        MaxQueue.prototype.delMax = function () {
            var max = this.queue[1];        //- 从根节点得到最大元素
            exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上,并且让长度索引减一
            this.queue.length = this.len+1; //- 删除最后一个节点
            sink(this.queue,1);             //- 下沉根节点,恢复堆的有序性
            return max;
        };
    
        MaxQueue.prototype.show = function () {
            console.log(this.queue);
        };
    
        MaxQueue.prototype.isEmpty = function () {
            return this.len==0;
        };

    示例图:

    堆上的优先队列操作

    堆排序

      理解了优先队列,堆排序的逻辑十分简单。第一步:让数组形成堆有序状态;第二步:把堆顶的元素放到数组最末尾,末尾的放到堆顶,在剩下的元素中下沉到正确位置,重复操作即可。

    代码如下:

        /**
         * 堆排序算法
         * @constructor
         */
        function HeapSort() {}
        HeapSort.prototype.sort = function (arr) {
            var len = arr.length;
            //由于arr[0]不使用,放到最后使得能够被排序
            //注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
            arr[len] = arr[0];
            //使用下沉来构造二叉堆
            for(var k=parseInt(len/2);k>=1;k--){
                sink(arr,k,len);
            }
            //不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
            while (len>1){
                exch(arr,1,len--);
                sink(arr,1,len);
            }
            //删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
            arr.splice(0,1);
        };

    示例图:

    堆排序

    完整代码

    Javascript实现

    /**
     * Created by YiYing on 2017/5/2.
     */
    (function (W) {
    
        /**
         * 优先队列
         * @constructor
         */
        function MaxQueue() {
            this.queue = [];                //- 存储基于堆的完全二叉树
            this.len   = 0;                 //- 存储于queue[1..len]中,queue[0]未使用
        }
    
        /**
         * 向优先队列中插入元素
         * @param val
         */
        MaxQueue.prototype.insert = function (val) {
            this.queue[++this.len] = val;    //- 从索引1开始添加元素
            //使新增元素上浮到树的正确位置
            swim(this.queue,this.len);
        };
    
        /**
         * 删除优先队列中的最大元素,并返回该元素
         * @returns {*}
         */
        MaxQueue.prototype.delMax = function () {
            var max = this.queue[1];        //- 从根节点得到最大元素
            exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上,并且让长度索引减一
            this.queue.length = this.len+1; //- 删除最后一个节点
            sink(this.queue,1);             //- 下沉根节点,恢复堆的有序性
            return max;
        };
    
        MaxQueue.prototype.show = function () {
            console.log(this.queue);
        };
    
        MaxQueue.prototype.isEmpty = function () {
            return this.len==0;
        };
    
        W.MaxQueue = MaxQueue;
    
    
        /**
         * 堆排序算法
         * @constructor
         */
        function HeapSort() {}
        HeapSort.prototype.sort = function (arr) {
            var len = arr.length;
            //由于arr[0]不使用,放到最后使得能够被排序
            //注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
            arr[len] = arr[0];
            //使用下沉来构造二叉堆
            for(var k=parseInt(len/2);k>=1;k--){
                sink(arr,k,len);
            }
            //不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
            while (len>1){
                exch(arr,1,len--);
                sink(arr,1,len);
            }
            //删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
            arr.splice(0,1);
        };
    
        W.HeapSort = HeapSort;
    
    
        //下标为k的元素上浮到正确位置
        function swim(arr,k) {
            while(k>1 && less(arr,parseInt(k/2),k)){
                //父节点索引
                var parentNode = parseInt(k/2);
                exch(arr,parentNode,k);
                k = parentNode;
            }
        }
    
        //下标为k的元素下沉到正确位置
        function sink(arr,k,len) {
            var len = len ||arr.length;
            while(2*k <= len){
                var j = 2*k;
                if(j<len && less(arr,j,j+1)) j++;
                if(!less(arr,k,j)) break;
                exch(arr,k,j);
                k = j;
            }
        }
    
        function less(arr,m,n) {
            //可根据不同的数据类型设置比对规则,比如json。这里适用于数字与字符串。
            return arr[m]<arr[n];
        }
    
        /**
         * 交换数组arr中m与n的位置
         * @param m
         * @param n
         */
        function exch(arr,m,n) {
            var swap    = arr[m];
            arr[m]      = arr[n];
            arr[n]      = swap;
        }
    
    
    })(window);
    
    //测试代码
    (function () {
        //优先队列测试,依次从大到小输出元素
        var q = new MaxQueue();
        q.insert(3);
        q.insert(33);
        q.insert(9);
        q.insert(21);
        while (!q.isEmpty()){
            console.log(q.delMax())
        }
    
        //堆排序测试代码
        var arr = [4,5,6,0,3,5,21,7,9,0,1];
        new HeapSort().sort(arr);
        console.log(arr);
    })();

    Java实现

    package com.algs;
    
    public class Heap {
        /**
         * 堆排序
         * @param pq
         */
        public static void sort(Comparable[] pq) {
            int n = pq.length;
            //构造堆结构
            for (int k = n/2; k >= 1; k--)
                sink(pq, k, n);
            //排序数组
            while (n > 1) {
                exch(pq, 1, n--);
                sink(pq, 1, n);
            }
        }
    
        //下沉元素
        private static void sink(Comparable[] pq, int k, int n) {
            while (2*k <= n) {
                int j = 2*k;
                if (j < n && less(pq, j, j+1)) j++;
                if (!less(pq, k, j)) break;
                exch(pq, k, j);
                k = j;
            }
        }
    
        //注意这里i和j都减去1
        private static boolean less(Comparable[] pq, int i, int j) {
            return pq[i-1].compareTo(pq[j-1]) < 0;
        }
        //注意这里i和j都减去1
        private static void exch(Object[] pq, int i, int j) {
            Object swap = pq[i-1];
            pq[i-1] = pq[j-1];
            pq[j-1] = swap;
        }
    
        private static void show(Comparable[] a) {
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
    
        public static void main(String[] args) {
            String[] a = {"S","O","R","T","E","X","A","M","P","L","E"};
            Heap.sort(a);
            show(a);
        }
    }
    

    总结

    1. 不稳定。
    2. 原地排序。
    3. 时间复杂度为NlogN
    4. 空间复杂度为l

    GitHub:https://github.com/AlbertKnag/algs-practice

    上一篇:排序算法07:三向快速排序

    展开全文
  • 现有的搜索引擎排序算法大多根据网页之间的链接关系进行排序,没有考虑原创和转载文章之间的优先次序。该文提出一种适用于专业搜索引擎的新型排序算法,在排序时优先考虑原创文章,使原创文章的搜索排名得以提高,有...
  • 八大排序算法(C语言实现)

    万次阅读 多人点赞 2021-05-09 13:50:26
    文章目录插入排序插入排序希尔排序选择排序选择排序排序交换排序冒泡排序快速排序并归排序并归排序 插入排序 插入排序 希尔排序 选择排序 选择排序排序 交换排序 冒泡排序 快速排序 并归排序 并归排序 ...
  • 本文主要讨论基于二叉堆数据结构的优先队列的实现以及衍生的堆排序 实现优先队列还可以使用栈,队列等数据结构,在此略 优先队列 主要解决问题 有时候比不需要元素全部有序,操作时,我们可能只需要处理最大...
  • 基数排序的概念 基数排序是桶排序的一种推广。 给定N个记录,每个记录的关键字为一整数,取值范围在0到M之间 之前提到的桶排序是在N远大于M的情况下使用的。 若如果M比N大很多,这时桶排序就需要M个桶,会造成...
  • 排序算法

    2019-09-03 23:13:22
    文章目录初级排序算法归并排序快速排序优先队列应用 初级排序算法 归并排序 快速排序 优先队列 应用 10种排序算法的对比分析中算法复杂度比较:
  • 排序算法是一个优秀的算法,但在实际应用中,快速排序的性能一般会由于堆排序。尽管如此,堆数据结构仍有许多应用。 优先队列是一种用来维护由一组元素构成的集合S的数据结构,每个元素都有相关的值,称为关键字...
  • 十大经典排序算法 十大经典排序算法-冒泡排序算法详解 十大经典排序算法-选择排序算法详解 十大经典排序算法-插入排序算法详解 十大经典排序算法-希尔排序算法详解 十大经典排序算法-快速排序算法详解 十大经典排序...
  • (1)若n较小(如n≤50),可采用直接插入或直接选择排序。  当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序),则应选用...
  • 今天的目的是循序渐进的分别复习字符串排序的低位优先算法、高位优先算法和三向快速排序算法。不过,在开始这三中算法之前,作为基础,我们先从一种字符串的分组算大讲起。一:字符串的分组算法/** 假设存在下列...
  • 学习完优先队列,发现一种新的排序算法,程序很简单,就是first in,largest out或first in ,least out 优先队列这个在#include中,priority_queue。默认情况下是largest out,加入greater就可以变成least out。 上...
  • C++中优先队列和sort自定义排序算法对比!! 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本...
  • 排序算法总结 | boren's blog排序算法总结boren's blog 首页 所有文章 关于作者排序算法总结Apr 6, 2018 | 技术人生 | 阅读排序,顾名思义,将数据按照某种规则排列起来.这种规则可以是根据基本的数值大小排序,也可以...
  • 在这篇之前,对常见的8中排序算法进行了梳理,《算法》第四版中的这一张图对各种排序算法的性能特点做了总结。   补充冒泡排序:稳定、原地排序、时间复杂度为n²,空间复杂度为1。其它: 快速排序是最快的通用...
  • 排序算法3-堆排序与优先队列

    千次阅读 2012-09-03 21:26:44
    首先说明一点,不要被名字所误导,优先队列并不是一种排序饿算法,而是一种数据结构。这个结构与一般的先入先出的队列不同,它每次出队的是优先级最大的元素。当一个指定优先级的元素入队时,能够很快的把它排到队列...
  • 一、十大排序算法复杂度对比   二、关于排序算法的总结 1、基数排序仅仅适用于整型数的排序,一般不与另外的排序方法一起比较。 2、关于算法的稳定性:不稳定的算法有 “快希选堆”——快速排序,希尔排序,...
  • Mckee排序算法(RCM) RCM算法 这是用于反向Cuthill Mckee排序算法(RCM)的Matlab代码。 RCM是一种将具有对称稀疏模式的稀疏矩阵置换为带宽小的带矩阵形式的算法。 实际上,与应用高斯消除的CM命令相比,这通常...
  • 通过深度优先算法进行拓扑排序(Java) package graph; //拓扑排序用深度优先算法实现 import java.io.IOException; import java.util.Scanner; import java.util.Stack; public class Topological { private ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 128,244
精华内容 51,297
关键字:

优先排序法