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

    万次阅读 多人点赞 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

     

     

     

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

             

    展开全文
  • 十大排序算法

    万次阅读 多人点赞 2021-08-20 13:37:46
    冒泡排序 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 重复步骤1~2,重复次数...

    有人问动图怎么做的,动图不是我做的哦,静图才是,推荐几个动画演示的网站:

    冒泡排序

    1. 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个
    2. 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数
    3. 重复步骤1~2,重复次数等于数组的长度,直到排序完成

    image-20210728113340011

    代码实现

    对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

    代码实现

    public class BubbleSort {
    
        public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                //array.length - 1 -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;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    }
    

    时间复杂度

    对于上面12个数据项,从第一个元素开始,第一趟比较了11次,第二趟比较了10次,依次类推,一直到最后一趟,就是:

    11 + 10 + 9 + 8 + 7 + 6 + 5  + 4 + 3  + 2 + 1  =  66次
    

    若有n个元素,则第一趟比较为(n-1)次,第二趟比较为(n-2)次,依次类推:

    (n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2
    

    在大O表示法中,去掉常数系数和低阶项,该排序方式的时间复杂度为:O(n2)

    算法稳定性

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。——百度百科

    在代码中可以看到,array[j + 1] = array[j]的时候,我们可以不移动array[i]array[j],所以冒泡排序是稳定的

    选择排序

    1. 找到数组中最大(或最小)的元素
    2. 将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换)
    3. 在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。

    image-20210728144443166

    代码实现

    对下面数组实现排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}

    动图演示

    选择排序

    代码实现

    public class SelectionSort {
    
        public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};
    
        public static int[] sort(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;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    很明显,和冒泡排序相比,在查找最小(或最大)元素的索引,比较次数仍然保持为O(n2)

    ,但元素交换次数为O(n)

    算法稳定性

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。举个例子,数组5,8,5,2,9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法

    image-20210728144637093

    插入排序

    当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

    插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

    1. 对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入。
    2. 为了给要插入的元素腾出空间,需要将插入位置之后的已排序元素在都向后移动一位。

    image-20210728162127494

    代码实现

    对下面数组实现排序:{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

    动图演示

    插入排序

    代码实现

    public class InsertionSort {
    
        public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            //待排序数据,改数据之前的已被排序
            int current;
            for (int i = 0; i < array.length - 1; i++) {
                //已被排序数据的索引
                int index = i;
                current = array[index + 1];
                //将当前元素后移一位
                while (index >= 0 && current < array[index]) {
                    array[index + 1] = array[index];
                    index--;
                }
                //插入
                array[index + 1] = current;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    在上面图示中,第一趟循环比较一次,第二趟循环两次,依次类推,则最后一趟比较n-1次:

    1 + 2 + 3 +… + n-1 = n*(n-1)/2
    

    也就是说,在最坏的情况下(逆序),比较的时间复杂度为O(n2)

    在最优的情况下,即while循坏总是假的,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n-1次,时间复杂度为O(n)

    算法稳定性

    在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变,所以插入排序是稳定的

    希尔排序

    一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动。

    希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序。

    希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序;然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组恰被分成一组,排序便完成了。这个不断缩小的数量,就构成了一个增量序列,这里的数量称为增量。

    image-20210729135834646

    代码实现

    public class ShellSort {
    
        public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};
    
        public static int[] sort(int[] array) {
            int len = array.length;
            if (len < 2) {
                return array;
            }
            //当前待排序数据,该数据之前的已被排序
            int current;
            //增量
            int gap = len / 2;
            while (gap > 0) {
                for (int i = gap; i < len; i++) {
                    current = array[i];
                    //前面有序序列的索引
                    int index = i - gap;
                    while (index >= 0 && current < array[index]) {
                        array[index + gap] = array[index];
                        //有序序列的下一个
                        index -= gap;
                    }
                    //插入
                    array[index + gap] = current;
                }
                //int相除取整
                gap = gap / 2;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    希尔排序的复杂度和增量序列有关。

    在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高,尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。

    从理论上说,只要一个数组是递减的,并且最后一个值是1,都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢?但是目前从数学上来说,无法证明某个序列是最好的。

    常用的增量序列:

    • 希尔增量序列 :{n/2, (n / 2)/2, …, 1},其中N为原始数组的长度,这是最常用的序列,但却不是最好的
    • Hibbard序列:{2k-1, …, 3,1}
    • Sedgewick序列:{… , 109 , 41 , 19 , 5,1} 表达式为9 * 4i- 9 * 2i + 1,i = 0,1,2,3,4…

    算法稳定性

    由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,如数组5,2,2,1,第一次排序第一个元素5会和第三个元素2交换,第二个元素2会和第四个元素1交换,原序列中两个2的相对前后顺序就被破坏了,所以希尔排序是一个不稳定的排序算法

    image-20210729165300142

    归并排序

    归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总。即“分”就是把一个大的通过递归成若干个小的,“治”就是将分后的结果在在一起。

    若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并。

    image-20210730115340519

    怎么分

    • 对于排序最好的情况来讲,就是只有两个元素,这时候比较大小就很简单,但是还是需要比较
    • 如果拆分为左右各一个,无需比较即是有序的。

    怎么治

    借助一个辅助空数组,把左右两边的数组按照大小比较,按顺序放入辅助数组中即可。

    以下面两个有序数组为例:

    归并排序

    代码实现

    public class MergeSort {
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            int mid = array.length / 2;
            //分成2组
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            //递归拆分
            return merge(sort(left), sort(right));
        }
    
        //治---合并
        public static int[] merge(int[] left, int[] right) {
            int[] result = new int[left.length + right.length];
            //i代表左边数组的索引,j代表右边
            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]) {//左边大于右边,取右边的
                    int a = right[j++];
                    result[index] = a;
                } else {//右边大于左边,取左边的
                    result[index] = left[i++];
                }
            }
            return result;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。

    归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间
    

    无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计,则:

    归并排序总时间 = 子序列排好序时间 + 合并时间
    

    假设处理的数据规模大小为 n,运行时间设为:T(n),则T(n) = n,当 n = 1时,T(1) = 1

    由于在合并时,两个子序列已经排好序,所以在合并的时候只需要 if 判断即可,所以n个数比较,合并的时间复杂度为 n。

    • 将 n 个数的序列,分为两个 n/2 的序列,则:T(n) = 2T(n/2) + n
    • 将 n/2 个数的序列,分为四个 n/4 的序列,则:T(n) = 4T(n/4) + 2n
    • 将 n/4 个数的序列,分为八个 n/8 的序列,则:T(n) = 8T(n/8) + 3n
    • 将 n/2k 个数的序列,分为2k个 n/2k 的序列,则:T(n) = 2kT(n/2k) + kn

    当 T(n/2k) = T(1)时, 即n/2k = 1(此时也是把n分解到只有1个数据的时候),转换为以2为底n的对数:k = log2n,把k带入到T(n)中,得:T(n) = n + nlog2n

    使用大O表示法,去掉常数项 n,省略底数 2,则归并排序的时间复杂度为:O(nlogn)

    算法稳定性

    从原理分析和代码可以看出,为在合并的时候,如果相等,选择前面的元素到辅助数组,所以归并排序是稳定的。

    快速排序

    快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的。

    从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作。

    问题

    若给定一个无序数组 [8, 5, 6, 4, 3, 1, 7, 2],并指定一个数为基准,拆分数组使得左侧的数都小于等于它 ,右侧的数都大于它。

    基准的选取最优的情况是基准值刚好取在无序区数值的中位数,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数,但是一般很难做到最优。基准的选取一般有三种方式:

    • 选取数组的第一个元素
    • 选取数组的最后一个元素
    • 以及选取第一个、最后一个以及中间的元素的中位数(如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为5, 所以选择5作为基准)。

    思路

    1. 随机选择数组的一个元素,比如 6 为基准,拆分数组同时引入一个初始指针,也叫分区指示器,初始指针指向 -1
    2. 将数组中的元素和基准数遍历比较
    3. 若当前元素大于基准数,不做任何变化
    4. 若当前元素小于等于基准数时,分割指示器右移一位,同时
      • 当前元素下标小于等于分区指示器时,当前元素保持不动
      • 当前元素下标大于分区指示器时,当前元素和分区指示器所指元素交换

    快速排序

    荷兰国旗问题

    荷兰的国旗是由红白蓝三种颜色构成,如图:

    若现在给一个随机的图形,如下:

    image-20210803151023780

    把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,这类问题称作荷兰国旗问题。

    对应leetcode:颜色分类

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
    

    分析:

    假如给定一个数组[8, 3, 6, 2, 5, 1, 7, 5],做如下操作:

    1. 随机选择数组的一个元素,比如 5 为基准,拆分数组同时引入一个左分区指示器,指向 -1,右分区指示器指向基准数(注:此时的基准数为尾元素)

    2. 若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,

      索引保持不变

    3. 若当前元素小于等于基准数时,左分区指示器右移一位,索引右移

      • 当前元素大于等于左分区指示器所指元素,当前元素保持不动
      • 当前元素小于左分区指示器所指元素,交换

    简单来说就是,左分区指示器向右移动的过程中,如果遇到大于或等于基准数时,则停止移动,右分区指示器向左移动的过程中,如果遇到小于或等于主元的元素则停止移动。这种操作也叫双向快速排序

    345345

    代码实现

    public class QuickSort {
    
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
    
        private static int[] sort(int[] array, int left, int right) {
            if (array.length < 1 || left > right) return null;
            //拆分
            int partitionIndex = partition(array, left, right);
            //递归
            if (partitionIndex > left) {
                sort(array, left, partitionIndex - 1);
            }
            if (partitionIndex < right) {
                sort(array, partitionIndex + 1, right);
            }
            return array;
        }
    
        /**
         * 分区快排操作
         *
         * @param array 原数组
         * @param left  左侧头索引
         * @param right 右侧尾索引
         * @return 分区指示器  最后指向基准数
         */
        public static int partition(int[] array, int left, int right) {
            //基准数下标---随机方式取值,也就是数组的长度随机1-8之间
            int pivot = (int) (left + Math.random() * (right - left + 1));
            //分区指示器索引
            int partitionIndex = left - 1;
            //基准数和尾部元素交换
            swap(array, pivot, right);
            //按照规定,如果当前元素大于基准数不做任何操作;
            //小于基准数,分区指示器右移,且当前元素的索引大于分区指示器,交换
            for (int i = left; i <= right; i++) {
                if (array[i] <= array[right]) {//当前元素小于等于基准数
                    partitionIndex++;
                    if (i > partitionIndex) {//当前元素的索引大于分区指示器
                        //交换
                        swap(array, i, partitionIndex);
                    }
                }
            }
            return partitionIndex;
        }
    
        /**
         * 双向扫描排序
         */
        public static int partitionTwoWay(int[] array, int left, int right) {
            //基准数
            int pivot = array[right];
            //左分区指示器索引
            int leftIndex = left - 1;
            //右分区指示器索引
            int rightIndex = right;
            //索引
            int index = left;
            while (index < rightIndex) {
                //若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,索引保持不变
                if (array[index] > pivot) {
                    swap(array, index, --rightIndex);
                } else if (array[index] <= pivot) {//当前元素小于等于基准数时,左分割指示器右移一位,索引右移
                    leftIndex++;
                    index++;
                    //当前元素小于等于左分区指示器所指元素,交换
                    if (array[index] < array[leftIndex]) {
                        swap(array, index, leftIndex);
                    }
                }
            }
            //索引和 L 指向同一个元素
            swap(array, right, rightIndex);
            return 1;
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY, 0, ARRAY.length - 1));
            System.out.println("====================双向排序==================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort(ARRAY2, 0, ARRAY2.length - 1));
        }
    }
    

    时间复杂度

    在拆分数组的时候可能会出现一种极端的情况,每次拆分的时候,基准数左边的元素个数都为0,而右边都为n-1个。这个时候,就需要拆分n次了。而每次拆分整理的时间复杂度为O(n),所以最坏的时间复杂度为O(n2)。什么意思?举个简单例子:

    在不知道初始序列已经有序的情况下进行排序,第1趟排序经过n-1次比较后,将第1个元素仍然定在原来的位置上,并得到一个长度为n-1的子序列;第2趟排序经过n-2次比较后,将第2个元素确定在它原来的位置上,又得到一个长度为n-2的子序列;以此类推,最终总的比较次数:

    C(n) = (n-1) + (n-2) + … + 1 = n(n-1)/2

    所以最坏的情况下,快速排序的时间复杂度为O(n^2)

    而最好的情况就是每次拆分都能够从数组的中间拆分,这样拆分logn次就行了,此时的时间复杂度为O(nlogn)。

    而平均时间复杂度,则是假设每次基准数随机,最后算出来的时间复杂度为O(nlogn)

    参考:快速排序的时间复杂度与空间复杂度

    算法稳定性

    通过上面的分析可以知道,在随机取基准数的时候,数据是可能会发生变化的,所以快速排序有不是稳定的情况。

    堆排序

    这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆。它具有以下特点:

    • 它是完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值

    知识补充

    二叉树

    树中节点的子节点不超过2的有序树

    image-20210804135913978

    满二叉树

    二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树。

    image-20210804140132004

    完全二叉树

    如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右。则深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。

    特点叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。需要注意的是,满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树。

    image-20210804144904950

    二叉堆

    二叉堆是一种特殊的堆,可以被看做一棵完全二叉树的数组对象,而根据其性质又可以分为下面两种:

    • 大根堆:每一个根节点都大于等于它的左右孩子节点,也叫最大堆
    • 小根堆:每一个根节点都小于等于它的左右孩子节点,也叫最小堆

    如果把一个数组通过大根堆的方式来表示(数组元素的值是可变的),如下:

    image-20210804180209118

    由此可以推出:

    • 对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1)

      如:对于 k = 1,其节点的对应数组为 5

      左子节点的位置为 3,对应数组的值为 3

      右子节点的位置为 4,对应数组的值为 2

    • 最后一个非叶子节点的位置为 (n/2) - 1,n为数组长度

      如:数组长度为6,则 (6/2) - 1 = 2,即位置 2 为最后一个非叶子节点

    给定一个随机数组[35,63,48,9,86,24,53,11],将该数组视为一个完全二叉树:

    image-20210804190655494

    从上图很明显的可以看出,这个二叉树不符合大根堆的定义,但是可以通过调整,使它变为最大堆。如果从最后一个非叶子节点开始,从下到上,从右往左调整,则:

    image-20210804224254053

    通过上面的调整,该二叉树为最大堆,这个时候开始排序,排序规则:

    • 将堆顶元素和尾元素交换
    • 交换后重新调整元素的位置,使之重新变成二叉堆

    image-20210804234843626

    代码实现

    public class HeapSort {
    
        public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    
        public static int[] sort(int[] array) {
            //数组的长度
            int length = array.length;
            if (length < 2) return array;
            //首先构建一个最大堆
            buildMaxHeap(array);
            //调整为最大堆之后,顶元素为最大元素并与微元素交换
            while (length > 0) {//当lenth <= 0时,说明已经到堆顶
                //交换
                swap(array, 0, length - 1);
                length--;//交换之后相当于把树中的最大值弹出去了,所以要--
                //交换之后从上往下调整使之成为最大堆
                adjustHeap(array, 0, length);
            }
            return array;
        }
    
        //对元素组构建为一个对应数组的最大堆
        private static void buildMaxHeap(int[] array) {
            //在之前的分析可知,最大堆的构建是从最后一个非叶子节点开始,从下往上,从右往左调整
            //最后一个非叶子节点的位置为:array.length/2 - 1
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                //调整使之成为最大堆
                adjustHeap(array, i, array.length);
            }
        }
    
        /**
         * 调整
         * @param parent 最后一个非叶子节点
         * @param length 数组的长度
         */
        private static void adjustHeap(int[] array, int parent, int length) {
            //定义最大值的索引
            int maxIndex = parent;
            //parent为对应元素的位置(数组的索引)
            int left = 2 * parent + 1;//左子节点对应元素的位置
            int right = 2 * (parent + 1);//右子节点对应元素的位置
            //判断是否有子节点,再比较父节点和左右子节点的大小
            //因为parent最后一个非叶子节点,所以如果有左右子节点则节点的位置都小于数组的长度
            if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
                maxIndex = left;
            }
            if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
                maxIndex = right;
            }
            //maxIndex为父节点,若发生改变则说明不是最大节点,需要交换
            if (maxIndex != parent) {
                swap(array, maxIndex, parent);
                //交换之后递归再次调整比较
                adjustHeap(array, maxIndex, length);
            }
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    堆的时间复杂度是 O(nlogn)

    参考:堆排序的时间复杂度分析

    算法稳定性

    堆的结构为,对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1),最大堆要求父节点大于等于其2个子节点,最小堆要求父节点小于等于其2个子节点。

    在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(最大堆)或者最小(最大堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,… 1 这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    参考:排序的稳定性

    思考

    对于快速排序来说,其平均复杂度为O(nlogn),堆排序也是O(nlogn),怎么选择?如下题:

    leetcode:数组中的第K个最大元素

    此题的意思是对于一个无序数组,经过排序后的第 k 个最大的元素。

    我们知道快速排序是需要对整个数组进行排序,这样才能取出第 k 个最大的元素。

    如果使用堆排序,且是最大堆的方式,则第k次循环即可找出第 k 个最大的元素,并不需要吧整个数组排序。

    所以对于怎么选择的问题,要看具体的场景,或者是两者都可。

    计数排序

    一种非比较排序。计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进行排序,而且待排序元素值分布较连续、跨度小的情况。

    如果一个数组里所有元素都是整数,而且都在0-k以内。对于数组里每个元素来说,如果能知道数组里有多少项小于或等于该元素,就能准确地给出该元素在排序后的数组的位置。

    如给定一个0~5范围内的数组[2,5,3,0,2,3,0,3],对于元素5为其中最大的元素,创建一个大小为(5-0+1 = 6)的计数数组,如果原数组中的值对应计数数组的下标,则下标对应计数数组的值加1。

    image-20210806112939098

    问题

    上面是通过数组的最大值来确定计数数组的长度的,但如果需要对学生的成绩进行排序,如学生成绩为:[95,93,92,94,92,93,95,90],如果按照上面的方法来处理,则需要一个大小为100的数组,但是可以看到其中的最小值为90,那也就是说前面 0~89 的位置都没有数据存放,造成了资源浪费。

    如果我们知道了数组的最大值和最小值,则计数数组的大小为(最大值 - 最小值 + 1),如上面数组的最大值为99,最小值为90,则定义计数数组的大小为(95 - 90 + 1 = 6)。并且索引分别对应原数组9095的值。我们把090的范围用一个偏移量来表示,即最小值90就是这个偏移量。

    image-20210806121018728

    代码实现

    public class CountSort {
    
        public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3};
        public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90};
    
        //优化前
        private static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //找出数组的最大值
            int max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
            }
            //初始化一个计数数组且值为0
            int[] countArray = new int[max + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            //填充计数数组
            for (int temp : array) {
                countArray[temp]++;
            }
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                //只要计数数组的下标不为0,就将计数数组的值从新写回原数组
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index;//计数数组下标对应元素组的值
                    countArray[n_index]--;//计数数组的值要-1
                    o_index++;
                } else {
                    n_index++;//上一个索引的值为0后开始下一个
                }
            }
            return array;
        }
    
        //优化后
        private static int[] sort2(int[] array) {
            if (array.length < 2) return array;
            //找出数组中的最大值和最小值
            int min = array[0], max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
                if (i < min) {
                    min = i;
                }
            }
            //定义一个偏移量,即最小值前面0~min的范围,这里直接用一个负数来表示
            int bias = 0 - min;
            //初始化一个计数数组且值为0
            int[] countArray = new int[max - min + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            for (int temp : array) {
                countArray[temp + bias]++;
            }
            //填充计数数组
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index - bias;
                    countArray[n_index]--;
                    o_index++;
                } else {
                    n_index++;
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
            System.out.println("=================优化排序====================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort2(ARRAY2));
        }
    }
    

    时间复杂度

    很明显,在排序过程中,我们至少遍历了三次原始数组,一次计数数组,所以它的复杂度为Ο(n+m)。因此,计数排序比任何排序都要块,这是一种牺牲空间换取时间的做法,因为排序过程中需要用一个计数数组来存元素组的出现次数。

    算法稳定性

    在新建的计数数组中记录原始数组中每个元素的数量,如果原始数组有相同的元素,则在输出时,无法保证元素原来的排序,是一种不稳定的排序算法。

    桶排序

    桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中。

    桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

    image-20210808133137559

    代码实现

    1. 找出数组中的最大值max和最小值min,可以确定出数组所在范围min~max

    2. 根据数据范围确定桶的数量

      • 若桶的数量太少,则桶排序失效
      • 若桶的数量太多,则有的桶可能,没有数据造成空间浪费

      所以桶的数量由我们自己来确定,但尽量让元素平均分布到每一个桶里,这里提供一个方式

      (最大值 - 最小值)/每个桶所能放置多少个不同数值+1

    3. 确定桶的区间,一般是按照(最大值 - 最小值)/桶的数量来划分的,且左闭右开

    public class BucketSort {
    
        public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};
    
        /**
         * @param bucketSize 作为每个桶所能放置多少个不同数值,即数值的类型
         *                   例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,
         *                   但是容量不限,即可以存放100个3
         */
        public static List<Integer> sort(List<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;
            //构建桶,初始化
            List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
            List<Integer> resultArr = new ArrayList<>();
            for (int i = 0; i < bucketCount; i++) {
                bucketArr.add(new ArrayList<>());
            }
            //将原数组的数据分配到桶中
            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--;
                    //对桶中的数据再次用桶进行排序
                    List<Integer> temp = sort(bucketArr.get(i), bucketSize);
                    for (int j = 0; j < temp.size(); j++)
                        resultArr.add(temp.get(j));
                }
            }
            return resultArr;
        }
    
        public static void print(List<Integer> array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
            System.out.println("============================================");
            print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
        }
    }
    

    时间复杂度

    桶排序算法遍历了2次原始数组,运算量为2N,最后,遍历桶输出排序结果的运算量为N,初始化桶的运算量为M。

    对桶进行排序,不同的排序算法算法复杂度不同,冒泡排序算法复杂度为O(N^2),堆排序、归并排序算法复杂度为O(NlogN),我们以排序算法复杂度为O(NlogN)进行计算,运算量为N/M * log(N/M) * M

    最终的运算量为3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系数,时间复杂度为O(N+M+N(logN-logM))

    参考:桶排序算法详解

    算法稳定性

    桶排序算法在对每个桶进行排序时,若选择稳定的排序算法,则排序后,相同元素的位置不会发生改变,所以桶排序算法是一种稳定的排序算法。

    基数排序

    常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成。

    基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果;当我们将所有的位排序后,整个数组就达到有序状态。基数排序不是基于比较的算法。

    基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能。那10就是它的基,同理二进制数字的基为2;对于字符串,如果它使用的是8位的扩展ASCII字符集,那么它的基就是256。

    基数排序有两种方法:

    • MSD 从高位开始进行排序
    • LSD 从低位开始进行排序

    对于大小范围为0~9的数的组合(若是两位数,就是个位数和十位数的组合),于是可以准备十个桶,然后放到对应的桶里,然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

    image-20210809173152835

    代码实现

    public class RadixSort {
    
        public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //根据最大值算出位数
            int max = array[0];
            for (int temp : array) {
                if (temp > max) {
                    max = temp;
                }
            }
            //算出位数digit
            int maxDigit = 0;
            while (max != 0) {
                max /= 10;
                maxDigit++;
            }
            //创建桶并初始化
            ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                bucket.add(new ArrayList<>());
            }
            //按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,每一轮排序都基于上轮排序后的结果
            int mold = 10;//取模运算
            int div = 1;//获取对应位数的值
            for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
                for (int j = 0; j < array.length; j++) {
                    //获取个位/十位/百位......
                    int num = (array[j] % mold) / div;
                    //把数据放入到对应的桶里
                    bucket.get(num).add(array[j]);
                }
                //把桶中的数据重新写回去,并把桶的元素清空,开始第二轮排序
                int index = 0;
                for (int k = 0; k < bucket.size(); k++) {
                    //桶中对应的数据
                    ArrayList<Integer> list = bucket.get(k);
                    for (int m = 0; m < list.size(); m++) {
                        array[index++] = list.get(m);
                    }
                    //清除桶
                    bucket.get(k).clear();
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    计数排序算法的时间复杂度是O(N+M),基数排序算法执行了k次计数排序,所以基数排序算法的时间复杂度为O(K(N+M))。

    算法稳定性

    从上面的分析可以看出,相同元素会按照顺序放进固定的桶内,取出的时候也是按照顺序取出来的,所以基数排序算法是一种稳定的排序算法。

    基数排序 vs 桶排序 vs 计数排序

    这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异

    • 基数排序:根据每一位的关键字来分配桶
    • 桶排序:存储一定范围的值
    • 计数排序:每个桶只存储一个类型值,但是数量不限

    image-20210810001026742

    展开全文
  • 排列组合算法

    千次阅读 2019-06-07 10:09:05
    发现一篇写的不错的排序组合算法,转载之 命题:多维数组的排列组合 或 多个数组之间的排列组合 命题场景: 现在有一批手机,其中颜色有[‘白色’,‘黑色’,‘金色’];内存大小有[‘16G’,‘32G’,‘64G’],...

    发现一篇写的不错的排序组合算法,转载之


    命题:多维数组的排列组合 或 多个数组之间的排列组合

    命题场景:

    现在有一批手机,其中颜色有[‘白色’,‘黑色’,‘金色’];内存大小有[‘16G’,‘32G’,‘64G’],版本有[‘移动’,‘联通’,‘电信’],要求写一个算法,实现[[‘白色’,‘16G’,‘移动’], [‘白色’,‘16G’,‘联通’] …]这样的组合,扩张,如果后面还有参数,比如再加一个[‘国行’,‘港版’],不改程序一样可以执行!

    不知道要实现的需求大家听懂了没有,下面我会一步步实现,教大家怎么写:

    最后得到的结果是一个数组里面包含若干个数组,看着挺复杂的,我们先实现一个简化版的,数组里面不是数组,而是字符串连接的结果,嗯,先一步步来吧:

    第一步,想想通过什么技术来实现,你看这数组之间不断的重组,很容易想到用回调函数,一遍一遍的执行,大致知道用什么技术,接下来就是写思路了,看看下面:

    // 执行组合排列的函数
        function doExchange(arr){
    
        }
    
        //执行
        var arr = [['a', 'b', 'c'], [1, 2, 3], ['x', 'y', 'z']];
        var arr1 = [['a','b','c']];
        //doExchange(arr);
        console.log(doExchange(arr));
    

    呐,我们建一个函数doExchange(),表示我们执行排序的主函数,然后当执行arr的时候,输出[‘a1x’,‘a1y’ …]这样的结果,如果是arr1呢?我们需要输出[‘a’,‘b’,‘c’],这好理解哈,现在的重点就是这个主函数了,下面主要讲主函数的实现过程

    // 执行组合排列的函数
        function doExchange(arr){
            var len = arr.length;
            // 当数组大于等于2个的时候
            if(len >= 2){
                
            }else{
                return arr[0];
            }
        }
    

    我们的思路是,当参数里面的数组长度大于2个,比如2个,3个或更多,就执行我们的组合代码,否则只有一个,就直接输出来呗

    如果是大于2个呢?我们的思路是先进行第一个和第二个的合并,网上有一种实现方式是,用多层for循环来嵌套,最终得到组合的值,这种估计大家也能感觉到,两三个还可以,多了就呵呵了,这里只是提一下,因为前两个比较好获取,合并之后呢,就相当于是
    2个数组合并成一个数组,然后这个数组再放倒参数数组中第一个位置,把原来前两个去掉,相当于是用这个数组替换前两个,没听懂哈,没关系,我们直接看代码

    if(len >= 2){
                // 第一个数组的长度
                var len1 = arr[0].length;
                // 第二个数组的长度
                var len2 = arr[1].length;
                // 2个数组产生的组合数
                var lenBoth = len1 * len2;
                //  申明一个新数组,做数据暂存
                var items = new Array(lenBoth);
                // 申明新数组的索引
                var index = 0;
                // 2层嵌套循环,将组合放到新数组中
                for(var i=0; i<len1; i++){
                    for(var j=0; j<len2; j++){
                        items[index] = arr[0][i] + arr[1][j];
                        index++;
                    }
                }
            }
    

    呐,这里我们先获取第一个和第二个数组的长度,然后计算出它们有多少种组合方式,然后新建一个暂存的数组,用来存我们组合得到的结果,后面就是用双层循环,做字符串连接,放到暂存数组中,没什么好说的

    我们的到了前两个的组合结果,依据我们的思路,是要把它和原来数组合并成一个新数组

    // 第一个数组的长度
                var len1 = arr[0].length;
                // 第二个数组的长度
                var len2 = arr[1].length;
                // 2个数组产生的组合数
                var lenBoth = len1 * len2;
                //  申明一个新数组,做数据暂存
                var items = new Array(lenBoth);
                // 申明新数组的索引
                var index = 0;
                // 2层嵌套循环,将组合放到新数组中
                for(var i=0; i<len1; i++){
                    for(var j=0; j<len2; j++){
                        items[index] = arr[0][i] + arr[1][j];
                        index++;
                    }
                }
                // 将新组合的数组并到原数组中
                var newArr = new Array(len -1);
                for(var i=2;i<arr.length;i++){
                    newArr[i-1] = arr[i];
                }
                newArr[0] = items;
    

    整体的思路就是这样,得到的新数组就是剩下的未组合的数组了,到这里大家应该就豁然开朗了,然后使用递归再次调用这个过程,这样不断组合成新数组,那这个新数组当参数时,如果数组的长度等于1了,就说明组合完了,就会执行后面的else语句,输出出来。

    整体代码贴出来感受一下:

    // 执行组合排列的函数
        function doExchange(arr){
            var len = arr.length;
            // 当数组大于等于2个的时候
            if(len >= 2){
                // 第一个数组的长度
                var len1 = arr[0].length;
                // 第二个数组的长度
                var len2 = arr[1].length;
                // 2个数组产生的组合数
                var lenBoth = len1 * len2;
                //  申明一个新数组,做数据暂存
                var items = new Array(lenBoth);
                // 申明新数组的索引
                var index = 0;
                // 2层嵌套循环,将组合放到新数组中
                for(var i=0; i<len1; i++){
                    for(var j=0; j<len2; j++){
                        items[index] = arr[0][i] + arr[1][j];
                        index++;
                    }
                }
                // 将新组合的数组并到原数组中
                var newArr = new Array(len -1);
                for(var i=2;i<arr.length;i++){
                    newArr[i-1] = arr[i];
                }
                newArr[0] = items;
                // 执行回调
                return doExchange(newArr);
            }else{
                return arr[0];
            }
        }
    
        //执行
        var arr = [['a', 'b', 'c'], [1, 2, 3], ['x', 'y', 'z']];
        var arr1 = [['a','b','c']];
        //doExchange(arr);
        console.log(doExchange(arr));
    

    执行arr和arr1的结果给大家截个图吧:

    在这里插入图片描述
    在这里插入图片描述
    我们简化版的组合算是完成了,可能也会有类似的需求,但是我们今天要讲的不是这样的需求,而是里面的每一个组合要是一个数组,这个怎么实现呢?

    突破点应该就在字符串连接那块了,原来是用的字符串连接,如果我们改成数组连接,不就行了吗?试试:

    for(var i=0; i<len1; i++){
        for(var j=0; j<len2; j++){
            if(arr[0][i] instanceof Array){
                items[index] = arr[0][i].concat(arr[1][j]);
            }else{
                items[index] = [arr[0][i]].concat(arr[1][j]);
            }
            index++;
         }
    }
    

    其他地方都没有改,就只是改了这里,但是这里第一次是要做数组判断的,因为刚开始是字符串,要转换成数组才能连接,这里注意一下,最终的代码如下:

    function doExchange(arr){
            var len = arr.length;
            // 当数组大于等于2个的时候
            if(len >= 2){
                // 第一个数组的长度
                var len1 = arr[0].length;
                // 第二个数组的长度
                var len2 = arr[1].length;
                // 2个数组产生的组合数
                var lenBoth = len1 * len2;
                //  申明一个新数组
                var items = new Array(lenBoth);
                // 申明新数组的索引
                var index = 0;
                for(var i=0; i<len1; i++){
                    for(var j=0; j<len2; j++){
                        if(arr[0][i] instanceof Array){
                            items[index] = arr[0][i].concat(arr[1][j]);
                        }else{
                            items[index] = [arr[0][i]].concat(arr[1][j]);
                        }
                        index++;
                    }
                }
                var newArr = new Array(len -1);
                for(var i=2;i<arr.length;i++){
                    newArr[i-1] = arr[i];
                }
                newArr[0] = items;
                return doExchange(newArr);
            }else{
                return arr[0];
            }
        }
    
        //
        var arr = [['a', 'b', 'c'], [1, 2, 3], ['x', 'y', 'z'],['手机']];
        var arr1 = [['a','b','c']];
        console.log(doExchange(arr));
    

    得到的结果:

    我后面又加了一个手机,同样是可以实现的,到这里就算写完了。

    本文转载自:https://www.cnblogs.com/liugang-vip/p/5985210.html

    展开全文
  • 十大经典排序算法-堆排序,计数排序,桶排序,基数排序 1-堆排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 2-计数排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 3-桶排序 ...

    养成习惯,先赞后看!!!

    你的点赞与关注真的对我非常有帮助.如果可以的话,动动手指,一键三连吧!!!

    十大经典排序算法-堆排序,计数排序,桶排序,基数排序

    前言

    这是十大经典排序算法详解的最后一篇了.
    还没有看多之前两篇文章的小伙伴可以先去看看之前的两篇文章:

    十大经典排序算法详解(一)冒泡排序,选择排序,插入排序
    十大经典排序算法详解(二)希尔排序,归并排序,快速排序

    这一篇文章真的耗费了我巨大的时间和精力,由于 堆排序是基于二叉树 的,所以写的篇幅比较大并且由于是关于树的,所以画图动态演示的工程量就进一步增加,其次就是因为计数排序,桶排序以及基数排序并不是基于比较的,所以算法的思想讲解相对于之前的基于比较的算法而言会稍微难一点.

    其次就是这次的调试过程也比之前多了很多需要注意的地方,这些我都会在下面的代码中通过注释的方式提醒大家.

    最后如果大家觉得我的文章写得还可以或者觉得文章对你有帮助的话,可以选择关注我的公众号:萌萌哒的瓤瓤,或者你也可以帮忙给文章来个一键三连吧.你的支持对我真的很有用.

    在这里插入图片描述

    1-堆排序

    算法思想:

    在介绍算法之前我们首先需要了解一下下面这些概念:什么是二叉树,什么是完全二叉树,什么是大根堆,什么是小根堆.

    • 二叉树

    学过数据结构的小伙伴肯定知道什么是二叉树,这部分主要是为那些可能还不太了解数据结构的小伙伴们说的.

    二叉树的定义就是每个结点至多能有两个子树,二叉树是一种最简单的树,下面我们举几个树的例子:

    在这里插入图片描述

    我们可以来哦稍微区分一下,很明显只有4号树并不是我们所说的二叉树,因为它的1号结点下有三棵子树,所以4号树并不是我们所说的二叉树.到这里,相信大家也已经基本了解二叉树得出概念了,那么接下来我们再来了解一下另一个概念完全二叉树.

    • 完全二叉树

    说到完全二叉树,就应该知道它首先应该满足二叉树的一些条件,就比如说每个节点至多只能有两个子树,那么除了这个条件以外,还需要什么条件才能称得上是完全二叉树呢.

    官方是这样说的: 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

    但是很明显说的太官方了,我们肯定需要简化一下概念.其实说白了就是在二叉树的基础上,所有的节点顺序必须要按照下面这样的顺序进行排列,否则就不能说是完全二叉树

    在这里插入图片描述

    并且每次必须是已经放满2的幂数之后才能放到下一层,并且必须是从每层最左边的节点开始添加节点,并且必须是先添加左节点在添加右节点.否则就不能称为是完全二叉树,这里呢,我们举几个反例,大家就知道我说的是什么意思了:

    在这里插入图片描述

    上面的这两棵树就是最明显的反例,看完这两棵树之后,相信大家就能更加了解什么是完全二叉树了.

    • 大根堆

    大根堆其实很容易理解,大根堆在完全二叉树的基础上就一条判定条件就是:每个根节点的值必须大于它的左孩子节点已经右孩子节点的值.满足这样条件的二叉树,我们就称这个二叉树是大根堆.当然了只要有一个节点不满足这样的情况,那么就不能称这是大根堆.

    举个例子,下面这棵二叉树就是一个大根堆:

    在这里插入图片描述

    举完正确的例子之后,我们当然也需要来举几个反例来帮助我们更好的理解什么是大根堆:

    在这里插入图片描述

    看完这两个反例之后相信大家就能更加理解什么是大根堆了.

    • 小根堆

    当然了,理解完什么是大根堆了之后,大家就能举一反三的了解什么叫做小根堆了.这里就不再给大家废话.

    在了解完上面的这些概念之后,我们就可以来讲解什么是堆排序了.

    堆排序的算法步骤其实很简单,总共就三步.

    • 1.将数组重构成大根堆

    • 2.将数组的队头元素与队尾元素交换位置

    • 3.对去除了队尾元素的数组进行重构,再次重构成大根堆

    之后重复上述2,3步骤,直到需要重构成大根堆的数组为空为止.

    算法的步骤的确简洁明了,其实大家看了也应该已经懂了.

    因为每次重构成大根堆之后,根据大根堆的特性,每个节点的值一定大于左右孩子节点的值,所以很明显大根堆的根节点就是二叉树中值最大的值同时也就是数组中最大的值.所以重构成大根堆之后交换数组队头与队尾元素的操作就是在将最大的元素进行定位.也就意味着这一轮结束之后,数组中已经确定了一个元素的最终位置了.

    算法的思想就是这样,谁都能说的出来,但是呢,堆排序的难点就是在于我们如何将数组重构成我们大根堆.这个就是堆排序的难点.

    那么接下来,我们就着重讲解一下重构大根堆的过程是怎么样的.

    首先我们需要明白一点就是我们一开始构建二叉树的时候遵循的是这样的原则: 从上往下,从左往右 .但是到了将二叉树重构成大根堆的时候我们的原则就必须要反过来了:从下往上,从右往左.这个大家动动小脑瓜应该就能理解了.

    显然我们每次对小子树进行重构成大根堆的操作时,最后都会使得最大的元素上移,对不对,既然大的元素是在上移的,那么很显然我们就应该从下往上开始构建.

    既然我们已经知道重构的顺序是什么样的之后,我们就需要再明白一点,那就是我们应该对哪些元素进行重构的操作呢?上面我们已经说过了,大根堆的一个硬性条件就是每个节点必需要大于它的左右孩子节点,那么很显然如果节点本身没有孩子节点的话,就不需要进行重构了.所以我们需要进行重构的元素必定包含孩子节点.并且结合我们上面所说重构顺序基本就可以得出一个结论:重构的元素就是最后一个非叶子节点之前的所有节点,包括该节点本身.,就比方下面这张图中红色圈圈的元素.

    在这里插入图片描述

    之后我们只需要通过循环,依次进行下面的操作:

    比较节点及其左右孩子节点,如果有孩子节点的值大于该节点,那么就交换两者的位置.
    这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    交换两者的位置之后我们还需要进行一个步骤 重新校验
    特别注意!!!特别注意!!!重复这个过程,直到最后一个元素为止.

    到这里堆排序的基本思想也就已经基本讲解完毕了,接下来就是通过图来动态的演示一下堆排序的过程,这样能够让大家更好的理解堆排序:

    这是第一轮堆排序:
    在这里插入图片描述)
    第二次堆排序:
    在这里插入图片描述)
    第三次堆排序:
    在这里插入图片描述)
    这里给大家模拟三次,大家应该就差不多懂这个流程了.主要是这图图画起来实在是太麻烦了.能力有限就只画这三次的了.在下面的代码里面,我还会着重讲重新校验的过程,大家如果这里还没理解的,也可以接着往下面看.

    算法的基本思想大家应该基本上就能理解了.那么我们再来稍微聊聊堆排序的一些特点:

    • 堆排序是不稳定的,这个其实还是比较好理解的.因为我们在进行小分支的调整时时有序的,但是之后可能会出现小分支扩大到大分支进行重新的调整,那么这时候就有可能会出现元素的相对位置混乱的情况.

      这个混乱的过程其实有点像我们之前所说的希尔排序,希尔排序也是小区间内的插入排序是有序的,但是一旦扩散到更大的区间进行二次的插入排序时就有可能造成相对位置混乱的情况.

      说的差不多了,那么我们接下来还是举一个例子来帮助大家更好的理解:

      在这里插入图片描述
      通过上面这张图,相信大家就能更好的理解堆排序为啥是不稳定的了.

    • 堆排序每轮排序都可以确定一个元素的最终位置,这个大家看我上面的演示图也能看出来.

    算法图解:

    在这里插入图片描述

    示例代码:
    这是我写的第一版的代码:

    //交换数组中的元素
    	public static void swap(int[]num ,int i,int j) {
    		int temp=num[i];
    		num[i]=num[j];
    		num[j]=temp;
    	}
    	//将待排序的数组构建成大根堆
    	public static void buildbigheap(int []num,int end) {
    		//从最后一个非叶子节点开始构建,依照从下往上,从右往左的顺序
    		for(int i=end/2;i>=0;i--) {
    			int left=2*i+1;
    			int right=2*i+2;
    			int big=i;
    			//判断小分支那个是大元素
    			if(left<end&&num[i]<num[left])
    //				swap(num, i, left);
    				i=left;
    			if(right<end&&num[i]<num[right])
    //				swap(num, i, right);
    				i=right;
    			swap(num, i, big);
    		}
    	}
    	public static void main(String[] args) {
    		int []num ={7,4,9,3,2,1,8,6,5,10};
    		long startTime=System.currentTimeMillis();  
    		//第一次构建大根堆
    		buildbigheap(num, num.length);
    		for(int j=num.length-1;j>0;j--) {
    			//交换队头已经排序得到的最大元素与队尾元素
    			swap(num, 0, j);
    			System.out.print("第"+(num.length-j)+"次排序:  ");
    			for(int k=0;k<num.length;k++) {
    				System.out.print(num[k]+" ");
    			}
    			System.out.println();
    			//交换结束之后,大根堆已经内破坏,需要开始重新构建大根堆
    			buildbigheap(num,j);
    		}
    		long endTime=System.currentTimeMillis(); 
    		System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); 
    	}
    

    在这里插入图片描述

    一开始我觉得我的代码是对的,并且运行出来的结果也和我预期的一样,但是当我自己画图以后画到这张图的时候我就知道算法还是有BUG的,这个BUG就是每次构建大根堆的时候:我们的确能够在每次构建大根堆的时候将最大的元素挑选出来,但是,我们在挑选出当前最大的元素之后,我们的大根堆真的还是大根堆吗,这里用上面画的图,我们就能看出来了:

    在这里插入图片描述

    很明显这个这一步我们的确已经将最大的元素挑选出来了,但是我们当前的已经不是大根堆了,所以我就在想我到底是哪一步做错了呢.之后我参考了网上的资料发现,该算法还有一个重点就是:如果我们发现根节点与孩子节点交换顺序之后,我们就需要重新检查交换之后的孩子节点以下的所有节点是否还满足大根堆的定义,因为可能我们交换后的孩子节点的值还是比他的孩子节点要小的.就比方上面那张图里我们所看到的.所以修改后的代码主要就是加上了重新校验的过程.

    修改后的第二版代码:

    //交换数组中的元素
    		public static void swap(int[]num ,int i,int j) {
    			int temp=num[i];
    			num[i]=num[j];
    			num[j]=temp;
    		}
    		//将待排序的数组构建成大根堆
    		public static void buildbigheap(int []num,int end) {
    			//从最后一个非叶子节点开始构建,依照从下往上,从右往左的顺序
    			for(int i=end/2;i>=0;i--) {
    				adjustnode(i, end, num);
    			}
    		}
    		//调整该节点及其以下的所有节点
    		public static void  adjustnode(int i,int end,int []num) {
    			int left=2*i+1;
    			int right=2*i+2;
    			int big=i;
    			//判断小分支那个是大元素
    			if(left<end&&num[i]<num[left])
    				i=left;
    			if(right<end&&num[i]<num[right])
    				i=right;
    			 if(i!=big) {
    			     //交换顺序之后需要继续校验
    				 swap(num, i, big);
    				 //重新校验,防止出现交换之后根节点小于孩子节点的情况
    				 adjustnode(i, end, num);
    			 }
    		}
    		public static void main(String[] args) {
    			int []num ={5,3,7,1,4,6,2};
    			long startTime=System.currentTimeMillis();  
    			//第一次构建大根堆
    			buildbigheap(num, num.length);
    			for(int j=num.length-1;j>0;j--) {
    				System.out.print("第"+(num.length-j)+"次排序前:  ");
    				for(int k=0;k<num.length;k++) {
    					System.out.print(num[k]+" ");
    				}
    				//交换队头已经排序得到的最大元素与队尾元素
    				swap(num, 0, j);
    				System.out.print("第"+(num.length-j)+"次排序后:  ");
    				for(int k=0;k<num.length;k++) {
    					System.out.print(num[k]+" ");
    				}
    				System.out.println();
    				//交换结束之后,大根堆已经被破坏,需要开始重新构建大根堆
    				buildbigheap(num,j);
    			}
    			long endTime=System.currentTimeMillis(); 
    			System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); 	
    		}
    

    在这里插入图片描述
    这里我们将这两个排序结果对比一下,大家就更加能了解重新校验步骤的重要性了.
    在这里插入图片描述
    相信经过我这样的讲解之后,大家一定能够更好的理解堆排序了.

    复杂度分析:

    理解完堆排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.

    • 时间复杂度

      堆排序的本质思想也是利用了二叉树的特性,所以根据他的遍历次数以及二叉树的层数可以得到堆排序的时间复杂度为O(N*logn),不仅仅是平情况是这样最好与最坏的情况都是如此.

    • 空间复杂度

      这个我们可以看到我们整个排序的过程中只增加一个存储交换元素的temp,所以堆排序的空间复杂是常量级别的仅为O(1).

    2-计数排序

    算法思想:
    计数排序最核心的思想就是计数序列中每个元素出现的次数,我们将每个元素的数量都记录下来之后.我们就可以通过按

    了解完计数排序的基本思想之后,我们就来看看看这个算法的实现步骤又是怎么样的呢?主要就是下面这几个步骤:

    • 1.第一次遍历序列,找出序列中的最大值以及最小值,然后根据最大值MAX最小值MIN创建一个MAX-MIN+1长度的数组.为什么创建这样长度的数组呢,因为只有创建了这样长度的数组,MIN-MAX区间内的每个元素才有对应的位置进行存放,如下图所示:
      在这里插入图片描述

    • 2.第二次遍历序列,我们每次遍历一个元素都将该元素所对应的区间数组对应的位置进行+1操作,这个步骤其实就是我们计数排序的核心----计数了.遍历结束之后,区间数组中的元素值就代表相应元素出现的次数,如下图所示:
      在这里插入图片描述

    • 3.最后一步就只需要按照区间数组中的次数一次将该元素打印出来即可.如下图所示:
      在这里插入图片描述

    计数排序的基本思想基本就是这样,按照惯例,还是通过下面的图来帮助大家更好的理解计数排序的基本思想:
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    了解完计数排序的基本思想之后,我们还是按照惯例分析一下计数排序算法的一些特点:

    -计数排序是稳定的 ,这个大家应该能很明显的看出来,因为计数排序本身并不是基于比较的算法.

    -计数排序需要的额外空间比较大,这个大家很明显的看出来,并且空间浪费的情况也会比较严重,因为一旦序列中MAX与MIN的差距过大,那么需要的内存空间就会非常大.并且假如序列中的元素都是散布在一个特定的区间内,那么内存空间浪费的情况也会非常明显.

    算法图解:

    在这里插入图片描述

    示例代码:

    public static void main(String[] args) {
    		int []num ={7,4,9,3,2,1,8,6,5,10};
    		long startTime=System.currentTimeMillis();  
    		int min=Integer.MAX_VALUE;
    		int max=Integer.MIN_VALUE;
    		//先找出数组中的最大值与最小值
    		for(int i=0;i<num.length;i++) {
    			if(num[i]<min)
    				min=num[i];
    			if(num[i]>max)
    				max=num[i];
    		}
    		//创建一个长度为max-min+1长度的数组来进行计数
    		int []figure=new int [max-min+1];
    		for(int i=0;i<num.length;i++) {
    			//计算每个数据出现的次数
    			figure[num[i]-min]++;
    		}
    		int begin=0;
    		//创建一个新的数组来存储已经排序完成的结果
    		int []num1=new int [num.length];
    		for(int i=0;i<figure.length;i++) {
    			//循环将数据pop出来
    			if(figure[i]!=0) {
    				for(int j=0;j<figure[i];j++) {
    					num1[begin++]=min+i;
    				}
    			}
    		}
    		System.out.println("数据范围:"+min+"~"+max);
    		System.out.println("计数结果:  ");
    		for(int i=0;i<num.length;i++)
    			System.out.println("         "+num[i]+"出现"+figure[num[i]-min]+"次");
    		System.out.print("排序结果:  ");
    		for(int i=0;i<num1.length;i++)
    			System.out.print(num1[i]+"   ");
    		System.out.println();
    		long endTime=System.currentTimeMillis(); 
    		System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); 
    	}
    

    在这里插入图片描述

    复杂度分析:

    理解完计数排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.

    • 时间复杂度

      计数排序很明显是一种通过空间来换时间的算法,因为我们可以很明显的看到计数排序需要三次遍历,两次遍历我们的原序列,第三次是遍历我们的区间数组.那么很明显时间复杂度一定是线性级别的但是因为第三次遍历的并不是我们的原序列,而是我们的区间数组,所以时间复杂度并不是我们的平常的O(n),而是应该加上我们遍历区间数组的时间,假设我们的区间数组长度为k的话,那么我们的时间复杂度就是O(n+k)

    • 空间复杂度

      上面我们已经说过了,计数排序本身就是一个通过空间来换取时间的算法,所以很明显他的空间复杂度就会很高.并且这个空间复杂度主要就取决于我们区间数组的长度,所以假设我们的区间数组长度为k的话,那么我们的空间复杂度就为O(k)

    3-桶排序

    算法思想:
    大家第一眼看到这个算法的名字时相信大家的反应应该和我是一样的,桶排序?排序怎么还需要用到桶呢?桶排序里的桶又是主要是干什么的呢?

    其实这个大家类比到我们平常生活中就能基本知道桶排序的桶是干嘛的呢?在我们的日常生活中,我们的桶一般都是用来装东西的,我们可能是用来装水,又或者是装钱的反正不管怎么样,我们的桶最后都是一个容器,是用来存储相应的物质的.

    在这里插入图片描述

    显然我们当前存在的只有我们的待排序的序列,那么我们的桶就是用来存储我们的序列中的元素的.就像下图所示:
    在这里插入图片描述

    可以看到我们把相应的元素放入相应的桶里面了.这个放入的规则是这样的:桶是从大到小排列的,并且每一个桶都会有一个数据范围,意思就是0号桶存放是1~ 2数据范围的数据,1号桶存放3~4数据范围的数据,2号桶存放吧5 ~6数据范围内的数据.详细的放入规则我会在下面的实现步骤里面说.这里大家先简单了解一下.

    这里大家要注意的一点就是,我们在把元素放入各自相应的桶里面的时候,是需要对桶内的序列进行排序,意思就是等到每个元素都放入相应的桶里面之后,桶里面相应的序列本身也已经有序了.就如下图所示:
    在这里插入图片描述
    可以看到上面,每个桶内的序列都已经排好序了,那么很显然我们最后就只需要按照桶的序号大小将桶内的元素打印出来,那么我们的序列就已经排好序了.

    说完桶排序的基本思想之后,我们接下来就说一下桶排序在代码上是如何实现的,大致有下面这几步:

    • 1.我们首先需要第一次遍历我们的序列,得到我们序列中的最大值MAX以及序列中的最小值MIN,找到我们序列中的最大值与最小值之后,那么我们就可以确定序列中的所有都是在MIN~MAX这个数据范围区间之中.

    • 2.第二步我们就是需要根据序列的数据范围来确定我们到底需要几个桶来存放我们的元素,这一步其实是比较关键的,因为桶的数量太多或者太少都会降低桶排序的效率.

      我们举两个例子:

      假设我们桶的数量太少,就比如说只有一个桶:
      在这里插入图片描述
      那么很显然我们的桶排序就又重新退化成我们前两篇内容里介绍的比较算法了.

      又假设我们桶的数量太多,就比如说有MAX-MIN+1个桶:
      在这里插入图片描述
      那么很显然这时候的桶排序又重新退化成了我们上面刚刚讲解过的计数排序了.

      所以说我们需要确定好一个适中的桶的数量,不然回就会出现我们上面所说到的几种情况.但是有没有一个特定的公式来确定桶的数量.所以我们还是只能自己确定桶的数量.但是有一个规则我们还是可以考虑进去的,那就是最好让元素平均的分散到每一个桶里.

    • 3.确定完桶的数量之后,我们就可以给每个桶来划分数据范围了.一般是这样划分的,(MAX-MIN+1)/桶的数量,得到的结果就是桶长.之后每个桶的数据范围就通过桶的编号以及桶长就可以确定每个桶的数据范围.就如下面的公式:

      左闭右开
      桶的数据范围=[MIN+(桶的编号-1)*桶长,MIN+桶的编号 *桶长)
      有了每个桶的数据范围时候,我们第二次遍历序列将每个元素存到相应的桶里面了.这个过程我们要注意,在往桶里面添加元素的时候,就需要在每个桶里面将元素排好序.

    • 4.当我们第二次遍历结束之后,我们就只需要按照桶的编号,在将该编号的桶里面的元素打印出来,桶排序就已经完成了.

    接下来我们还是通过下面的图来动态演示一下桶排序的过程:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    了解完桶排序的基本思想之后,按照惯例我们还是来简单分析一下他的一些特点:

    • 桶排序是稳定的,原因和上面计数排序的理由是一样的.
    • 桶排序也是一个通过空间换取时间的算法,但是他的空间复杂度是可以控制的.就像我们上面说的主要就是控制桶的数量.如果桶的数量设置的合理,既能降低时间复杂度,也能降低空间复杂度.

    算法图解:
    在这里插入图片描述

    示例代码:

    //在链表中添加元素的同时需要进行元素的排序
    	public static void sort(ArrayList<Integer>list,int i) {
    		if(list==null)
    			list.add(i);
    		//这里采用的排序方式为插入排序
    		else {
    			int flag=list.size()-1;
    			while(flag>=0&&list.get(flag)>i) {
    				if(flag+1>=list.size())
    					list.add(list.get(flag));
    				else  
    					list.set(flag+1, list.get(flag));
    				flag--;
    			}
    			if(flag != (list.size()-1))
    				//注意这里是flag+1,自己可以尝试将这里换成flag看看,会出现数组越界的情况
    			    list.set(flag+1, i);
    			else
    				list.add(i);
    		}
    	}
    	public static void Bucketsort(int []num,int sum) {
           //遍历得到数组中的最大值与最小值
    		int min=Integer.MAX_VALUE;
    		int max=Integer.MIN_VALUE;
    		for(int i=0;i<num.length;i++) {
    			min = min <= num[i] ? min: num[i];
    	        max = max >= num[i] ? max: num[i];
    		}
    		//求出每个桶的长度,这里必须使用Double
    		double size=(double)(max-min+1)/sum; 
    		ArrayList<Integer>list[]=new ArrayList[sum];
    		for(int i=0;i<sum;i++) {
    			list[i]=new ArrayList<Integer>();
    		}
    		//将每个元素放入对应的桶之中同时进行桶内元素的排序
    		for(int i=0;i<num.length;i++) {
    			System.out.println("元素:"+String.format("%-2s", num[i])+", 被分配到"+(int)Math.floor((num[i]-min)/size)+"号桶");
    			sort(list[(int)Math.floor((num[i]-min)/size)], num[i]);
    		}
    		System.out.println();
    		for(int i=0;i<sum;i++) {
    			System.out.println(String.format("%-1s", i)+"号桶内排序:"+list[i]);
    		}
    		System.out.println();
    		//顺序遍历各个桶,得出我们 已经排序号的序列
    		for(int i=0;i<list.length;i++) {
    			if(list[i]!=null){
    				for(int j=0;j<list[i].size();j++) {
    					System.out.print(list[i].get(j)+" ");
    				}
    			}
    		}
    		System.out.println();
    		System.out.println();
    	}
    	public static void main(String[] args) {
    		
    		int []num ={7,4,9,3,2,1,8,6,5,10};
    		long startTime=System.currentTimeMillis();
    		//这里桶的数量可以你自己定义,这里我就定义成了3
    		Bucketsort(num, 3);
    		long endTime=System.currentTimeMillis(); 
    		System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); 
    	}
    

    在这里插入图片描述
    这里的时间是不准确的,因为我需要将每轮排序的结果打印出来给大家看,所以会多花费一些时间,如果大家想要看真实的时间的话,大家可以把我打印结果的代码注释掉再看看算法的执行时间.

    复杂度分析:

    理解完桶排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.

    • 时间复杂度

      桶排序的时间复杂度和上面的计数排序是一样的,同样也是线性级别的,但是也是增加了桶的时间,所以也是O(n+k)

    • 空间复杂度

      上面我们已经说过了,桶排序本身也是一个通过空间来换取时间的算法,所以很明显他的空间复杂度就会很高.并且这个空间复杂度主要就取决于桶的数量以及桶的范围,所以假设有k个桶的话,那么空间复杂度就为O(n+k)

    4-基数排序

    算法思想:

    基数排序的实现步骤非常好理解,但是想要真正理解他的算法思想就稍微有点难度了.那么接下来就来讲解基数排序的算法思想.

    首先基数排序是根据数位来进行排序的.他是从个位开始,然后按照每一位的数进行排序,如下图所示:
    在这里插入图片描述

    排完序之后就往前进一位,然后再将所有的数按照这一位所在的数进行排序,如下图所示:
    在这里插入图片描述

    重复这个过程直到所有的位数都已经被排过序了.如下图所示:
    在这里插入图片描述

    并且如果这个过程中碰到某个数在这个为上没有数的话就进行补零操作,将该位看成是0.就比方下图我用红框圈出来的部分:
    在这里插入图片描述
    等到所有的位数都已经排序完毕之后,我们就可以看到我们已经排序好的序列了.

    这个过程相信大家肯定都很好理解,但是相信大家如果是第一次看这个算法的肯定会有和我当初一样的困惑,那就是为什么基数排序选择的是从低位到高位来进行排序的呢,而不是像我们平常比较数据的大小一样,从高位到低位来比较呢?

    这里呢我们先不讲为什么,我们先看下面这两个案例:

    • 从高位到低位进行比较
    原序列百位排好序后十位排好序后个位排好序后
    329839657839
    457720457329
    657657355657
    839457839457
    436436436436
    720329720355
    355355329720
    • 从低位到高位进行比较
    原序列个位排好序后十位排好序后百位排好序后
    329720720329
    457355329355
    657436436436
    839457839457
    436657355657
    720329451720
    355839657839

    对比看了上面两个例子之后相信大家就知道了,很明显我们看到如果是从该我到低位来进行比较的话,我们会发现比较到最后之后序列仍然是无序的,但是从低位到高位进行比较的话,我们就会发现序列到最后已经排好序了.

    是不是很奇怪,同样的执行过程,只不过执行的顺序发生了改变,为什么结果就回产生这样的结果呢?产生这个差异的重点就是在我们忽略了一个问题,那就是我们在进行高位到低位比较的时候,高位的权重是高于低位的.就比方下图所示:
    在这里插入图片描述
    正是因为这个原因,所以我们采取的是从低位到高位比较的过程.

    说完基本思想之后,我们来说一下算法的实现步骤:

    • 1.我们第一次遍历序列.找出序列中的最大值MAX,找到MAX之后我们可以确定我们需要比较多少数位了.

    • 2.这时候我们就需要按照元素在该位数对应的数字将元素存入到相应的容器之中.如下图所示:
      在这里插入图片描述

    • 3.之后我们再按照容器的顺序将元素重新弹出构成我们接下来需要排序的序列,如下图所示:
      在这里插入图片描述
      这个从容器弹出的过程需要注意一点,那就是遵循先进先出的原则,所以这个容器选择队列或者是链表比较合适,不能选择栈,因为栈是先进后出,拿取元素的时候回非常麻烦.

    • 4.最后只需要重复2,3步骤,直到最高位也比较完毕,那么整个基数排序就已经完成了.

    接下来我们还是通过下面的图来动态演示一下基数排序的过程:
    个位排序:
    在这里插入图片描述
    十位排序:
    在这里插入图片描述
    百位排序:
    在这里插入图片描述
    千位排序:
    在这里插入图片描述

    在了解完基数排序的基本思想之后,按照惯例我们还是来简单分析一下基数排序的特点:

    • 基数排序是稳定的,原因和桶排序以及计数排序的原因一样.

    算法图解:

    在这里插入图片描述

    示例代码:

    //将所有的数组合并成原来的数组
    	public static void merge(ArrayList<Integer> list[],int num[]) {
    		int k=0;
    		for(int i=0;i<list.length;i++) {
    			if(list[i]!=null) {
    				for(int j=0;j<list[i].size();j++) {
    					num[k++]=list[i].get(j);
    					System.out.print(num[k-1]+" ");
    				}
    			}
    			//合并完成之后需要将链表清空,否则元素会越来越多
    			list[i].clear();
    		}
    		System.out.println();
    	}
    	//将所有的元素分散到各个链表之中
    	public static void split(ArrayList<Integer> list[],int num[],int k) {
    		for(int j=0;j<num.length;j++) {
    			list[num[j]/k%10].add(num[j]);
    		}
    		System.out.println("-----------------------------------------------------------------------");
    		System.out.println("个位开始数,第"+(String.valueOf(k).length())+"位排序结果:");
    		for(int j=0;j<10;j++) {
    			System.out.println((String.valueOf(k).length())+"号位,数值为"+j+"的链表结果:"+list[j]);
    		}
    	}
    	public static void main(String[] args) {
    		ArrayList<Integer>list[]=new ArrayList [10];
    		for(int i=0;i<10;i++) {
    			list[i]=new ArrayList<Integer>();
    		}
    		int []num ={7,14,9,333,201,1,88,6,57,10,56,74,36,234,456};
    		long startTime=System.currentTimeMillis();  
    		int max=Integer.MIN_VALUE;
    		//第一次遍历获得序列中的最大值
    		for(int i=0;i<num.length;i++) {
    			if(num[i]>max)
    				max=num[i];
    		}
    		int k=1;
    		for(int i=0;i<String.valueOf(max).length();i++) {
    			split(list, num, k);
    			System.out.println("第"+(i+1)+"次排序");
    			merge(list, num);
    			k=k*10;
    		}
    		long endTime=System.currentTimeMillis(); 
    		System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); 
    	}
    

    在这里插入图片描述

    复杂度分析:

    理解完基数排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.

    • 时间复杂度

      看完我们上面的动图演示之后我们可以看到基数排序只需要根据最大元素的位数,遍历相应次数的序列即可,所以我们可以确定基数排序的时间复杂度一定是线性级别的,但是虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k)

    • 空间复杂度

      空间复杂度我们也可以看出来,主要就是取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)

    到这里十大经典排序算法详解的内容就已经全部讲解完毕了.这一次文章不管是在内容的质量上或者是在文章的排版上,都是目前工作量比较大的一期.所以如果大家觉得文章还行或者觉得文章对你有帮助的话,UP希望能关注一下我的公众号:萌萌哒的瓤瓤,或者觉得关注公众号麻烦的话,也可以给我的文章一键三连.新人UP真的很需要你的支持!!!

    在这里插入图片描述

    不点在看,你也好看!

    点点在看,你更好看!

    展开全文
  • 排列组合算法之 字典序排序算法

    千次阅读 2015-12-24 14:42:41
    字典序法就是按照字典排序的思想逐一产生所有排列。例如,由1,2,3组成的所有排列,从小到大的依次为: 123,132,213,231,312,321 由1,2,3,4组成的所有排列: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, ...
  • 打开算法大门,从排序开始
  • 今天研究了一下比较排序算法中的归并算法和快速排序算法,这两种算法基本上都采用了分治算法的思想。首先,我们谈谈归并算法。 归并算法每次均将序列分为两半分别处理,最终合并成一个序列。归并算法可以把序列看成...
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
  • 排列生成算法,序数法,C语言源代码 首先生成中介数,由中介数确定排列。
  • 排序、排列组合算法python代码

    千次阅读 2013-09-26 16:53:19
    刚开始学习时跑过几个小代码,包括二分查找、快速排序、排序组合等,主要还是复习这些算法的同时,学习简单的python代码书写与调试,这里将这些小代码贴上,仅供好玩! 二分查找:python代码 Fibonacci数列...
  • 本文介绍了常用的排列组合算法,包括全排列算法,全组合算法,m个数选n个组合算法等。 2. 排列算法 常见的排列算法有: (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 (E)递归法 介绍常用的两种...
  • 排序算法

    2013-04-24 09:53:40
    排序算法总结(from 维基) 排序算法总表 理论 计算复杂性理论 大O符号 全序关系 列表 稳定性 比较排序 自适应排序 排序网络 整数排序   交换排序 冒泡...
  • 归并排序1.2-路归并排序算法 “归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。 基本操作:假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序的长度为1,然后两两归并,得到[n/2]个...
  • 算法——序列组合排序

    千次阅读 2021-04-21 14:19:02
    现要求把x1和x2组合成一个列表xs,y1和y2组合成一个列表ys,并且要求xs必须从小到大排序,ys必须与xs同步变化。 1、不使用sorted函数 def compare(x1, y1, x2, y2, i, j): global xs, ys, itop, jtop if x1[i] [j]...
  • (1)针对插入排序、归并排序和快速排序算法,编写完整程序实现三种排序算法。 (2)采用随机生成测试用例的方法生成三组算法测试数据集。三组测试数据集的规模分别是:20000个数据、50000个数据、200000个数据。 ...
  • 采用排序组合差分方法解决排列组合问题,构造了随机城市的TSP问题,供初学者学习使用
  • 数据结构排序算法大总结(C语言),总结整理直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序,简单选择排序、堆排序、归并排序、基数排序九大排序算法以及外排序算法思想,结合图片演示原理,含源码。
  • 常见的7种排序算法

    万次阅读 多人点赞 2018-06-10 11:37:21
    最简单的一种排序算法。假设长度为n的数组arr,要按照从小到大排序。则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的两个元素进行比较,如果位于数组左端的元素...
  • java排序算法_012组合排序

    千次阅读 2012-12-05 21:39:12
    package wzs.sort; //用1、2、3、4、5这五个数字,用java写一个main函数,打印出所有不同的排列,如:51234、41235等。 public class Test_wzs012 { public static void main(String[] args) ...
  • 易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合
  • 快速排序算法

    2018-05-27 11:35:40
    快速排序算法是什么?快速排序算法是一种冒泡循环的一种改进。使用时运用递归(自己调用自己)的方式是自身变成一个有序序列。快速排序算法是一种不稳定的数组,有多个相同的值会使结果产生变动。快速排序算法什么...
  • 排序算法系列:冒泡排序与双向冒泡排序

    万次阅读 多人点赞 2016-01-29 15:25:32
    **排序算法**应该算是一个比较热门的话题,在各个技术博客平台上也都有一些博文进行了一定程度的讲解。但还是希望能从自我完善的角度出发,可以更详细、全面、形象地表达这些算法的精髓。本文就先从最简单的冒泡排序...
  • 本篇文章讲解三个高级排序算法,分别为希尔排序、归并排序、快速排序。虽然它们的思想很复杂,但真的运用得非常得巧妙,我会用丰富的例子以及动图来让大家轻松地理解并掌握。
  • 排序算法总结

    千次阅读 2016-12-24 15:19:16
    基础的排序算法包含冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序及快速排序。 根据实现类型可分为插入排序类、选择排序类、交换排序类及归并排序类。 2.排序算法的综合分析 各算法排序方式、...
  • 经典十大排序算法【Java版完整代码】写在前面的话十大排序算法对比冒泡排序快速排序直接选择排序排序归并排序插入排序希尔排序计数排序排序基数排序 写在前面的话        ...
  • python算法排序算法和查找算法

    千次阅读 2019-03-17 09:25:10
    一、排序算法 定义 排序算法(英语:Sorting algorithm)是一种能将一串 数据依照特定顺序进行排列的一种算法。 1.冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列...
  • 算法之排列与组合算法

    千次阅读 2016-03-27 13:09:06
    本文介绍了常用的排列组合算法,包括全排列算法,全组合算法,m个数选n个组合算法等。 2. 排列算法 常见的排列算法有: (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 (E)...
  • 排序组合,AS实现穷举算法

    千次阅读 2011-12-02 01:43:11
    算法如下:   private function compoud(N:uint, C:uint):void { var pickIndex:int = 0; var X:int=1; var Y:int=1; var P:int=1; var i:int=0; var arr:Array = new
  • 使用排序化简组合生成算法

    千次阅读 2010-01-17 18:57:00
    组合问题在日常生活中随处可见,先来看一个摘于《离散数学》(第六版,Richard Johnsonbaugh著)的例子: 摇滚乐队“Unhinged Universe”录制了n段视频节目,时间长度分别为t1 ,t2 ,t3 ,…,tn 秒。一盘磁带可以容纳...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 144,722
精华内容 57,888
关键字:

排序组合算法