排序 订阅
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1] 展开全文
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1]
信息
排序算法
快速排序、希尔排序、堆排序等
应用学科
数学 计算机
分    类
稳定排序等
中文名
排序
性    质
计算机内经常进行的一种操作
外文名
sequence
排序概念
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。 [2]  快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 [1]  ◆稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,归属于不稳定排序。 [3]  ◆就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),则称为就地排序。
收起全文
精华内容
参与话题
问答
  • 八大排序算法

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

     

     

     

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

             

    展开全文
  • 经典算法---冒泡排序

    万次阅读 多人点赞 2014-09-24 15:58:50
    原文链接: 冒泡排序---经典排序算法 | 逍遥游 冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序...

    原文链接: 冒泡排序---经典排序算法 | 逍遥游

     

    冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序算法。

     

    算法原理

    冒泡排序的原理(以递增序为例)是每次从头开始依次比较相邻的两个元素,如果后面一个元素比前一个要大,说明顺序不对,则将它们交换,本次循环完毕之后再次从头开始扫描,直到某次扫描中没有元素交换,说明每个元素都不比它后面的元素大,至此排序完成。

    由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。

     

    时间复杂度

    若文件的初始状态是排好序的的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数 M 均达到最小值(Cmin = n-1、Mmin = 0)

    所以,冒泡排序最好的时间复杂度为O(N)。


      若初始文件是反序的,需要进行N趟排序。每趟排序要进行 C = N-1次关键字的比较(1≤i≤N-1)和总共(Mmax = (N*(N-1))/2)次的移动(移动次数由乱序对的个数决定,即多少对元素顺序不对,如 1 3 4 2 5 中共有(3,2)、(4,2)两个乱序对),在这种情况下,比较和移动次数均达到最大值(Cmax =N*(N-1) + Mmax=(N*(N-1))/2 = O(N^2))。所以,冒泡排序的最坏时间复杂度为O(N^2)

     

    综上,冒泡排序总的平均时间复杂度为O(N^2)。

    算法稳定性

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。如果两个相等的元素相邻,那么根据我们的算法。它们之间没有发生交换;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

     

    算法改进

    由于冒泡排序算法还是比较慢的,所以有很多人对在此基础上进行了改进,我只简单介绍一下我所知道的。

    第一种是上浮操作与下沉操作相结合。传统的冒泡排序只有上浮操作,如果碰到一些很特殊的数据就会显得笨一点,例如(2、3、4、5、1)这个数列按增序排列,那么按照普通冒泡算法就要扫描5趟,可是我们一眼就看出来直接把 1 挪到第一个就行了,扫描 5 次实在是太笨了,于是我们在每次上浮操作后加上一个下沉操作,这样就更快了。

    第二中改进是减少无效比较的次数。所谓无效比较就是当我们已知结果却还要去比较。如果我们多观察冒泡排序的中间过程,我们就会发现,末尾的一些元素在一定次数的扫描后已经到达最终位置了(因为每次扫描后都至少会有一个新的元素到达最终位置),再比较就会造成无效比较。改进方法是,记录下每次扫描中发生交换的最后一个元素位置,下一次扫描就到这里为止。

    可是,无论怎么改进,冒泡排序的时间复杂度都是O(N^2)。

     

    下面给出冒泡排序的C++参考代码和下载地址。

     

     

    //冒泡排序部分,参数形式与标准库的快排一样
    
    //ps:(point start)所需排序的数据首地址
    
    //pe:(point end)  所需排序的数据第一个无效地址
    
    //cmp:自定义的比较函数
    
    int sort(int *ps,int *pe,bool(*cmp)(int,int))
    
    {
    
    //用以判断某次循环后是否有元素位置发生变化
    
        bool flag=true;
    
     
    
        while(flag)
    
        {
    
            flag=false;//假设没有交换
    
     
    
            //上浮过程
    
            for(int i=1;i<pe-ps;i++)//注意:i从1开始
    
            {
    
                if(cmp(ps[i],ps[i-1]))
    
                {
    
                    swap(ps[i],ps[i-1]);
    
                    flag=true;//有元素发生交换,说明排序可能没有结束
    
                }
    
            }
    
        }
    
        return 0;
    
    }
    

     

     

     

     

    更详细的代码,请点击这里下载。

     

    来源:逍遥游,欢迎分享本文,转载请保留出处!

    展开全文
  • 程序员那些必须掌握的排序算法(上)

    万次阅读 多人点赞 2019-08-17 16:03:39
    现在的IT行业并不像以前那么好混了,从业人员过多,导致初级程序员过剩,这也间接导致了公司的招聘门槛越来越高,要求程序员掌握的知识也越来越多。 算法也是一个争论了很久的话题,程序员到底该不该掌握算法?...

    现在的IT行业并不像以前那么好混了,从业人员过多,导致初级程序员过剩,这也间接导致了公司的招聘门槛越来越高,要求程序员掌握的知识也越来越多。
    算法也是一个争论了很久的话题,程序员到底该不该掌握算法?不同的人有不同的答案,而事实上,很多公司都对算法有一定的要求,有些公司直接在面试的时候便会要求面试者手写算法题。这就对程序员的技术要求产生了很大的考验,所以面对如今的大环境,我们必须掌握算法,才能在今后的工作中占据一席之地。
    那么接下来,我就简单介绍一下几个排序算法,希望对你们有所帮助。

    1.冒泡排序

    冒泡排序(Bubble Sort),是一种较简单的排序算法。
    它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
    这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
    演示:
    在这里插入图片描述
    代码如下:

    @Test
    public void bubbleSort() {
    	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	// 统计比较次数
    	int count = 0;
    	// 第一轮比较
    	for (int i = 0; i < arr.length - 1; i++) {
    		// 第二轮比较
    		for (int j = 0; j < arr.length - 1 - i; j++) {
    			if (arr[j] > arr[j + 1]) {
    				// 交换位置
    				int temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    			count++;
    		}
    	}
    	System.out.println(Arrays.toString(arr));
    	System.out.println("一共比较了:" + count + "次");
    }
    

    运行结果:

    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    一共比较了:105次
    

    这段代码相信大家都能够写出来,一般冒泡排序也就是这样写。但是这段程序有个缺点,就是当排序过程中已经将数组元素排序完成,但此时它仍然会去比较,这就做了无用功了,所以我们可以通过一个boolean变量来优化这段代,上面的程序中我们已经得出了比较次数为105次。
    优化代码:

    @Test
    public void bubbleSort() {
    	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	// 统计比较次数
    	int count = 0;
    	for (int i = 0; i < arr.length - 1; i++) {
    		boolean flag = true;
    		for (int j = 0; j < arr.length - 1 - i; j++) {
    			if (arr[j] > arr[j + 1]) {
    				// 交换位置
    				int temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    				flag = false;
    			}
    			count++;
    		}
    		if(flag) {
    			break;
    		}
    	}
    	System.out.println(Arrays.toString(arr));
    	System.out.println("一共比较了:" + count + "次");
    }
    

    运行结果:

    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    一共比较了:95次
    

    我们首先在开始循环时定义了一个boolean变量为true,然后如果元素之间进行了交换,就将值置为false。所以,我们就可以通过这个boolean变量来判断是否有元素进行了交换。如果boolean变量为true,则证明没有元素进行交换,那么久说明此时的数组元素已经完成排序,那么跳出外层循环即可,否则就继续排序。通过结果也可以看出,比较次数确实是减少了很多。

    2.选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
    演示:
    在这里插入图片描述
    代码如下:

    @Test
    public void SelectionSort() {
    	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	for (int i = 0; i < arr.length - 1; i++) {
    		int index = i;
    		for (int j = 1 + i; j < arr.length; j++) {
    			if (arr[j] < arr[index]) {
    				index = j;// 保存最小元素的下标
    			}
    		}
    		// 此时已经找到最小元素的下标
    		// 将最小元素与前面的元素交换
    		int temp = arr[index];
    		arr[index] = arr[i];
    		arr[i] = temp;
    	}
    	System.out.println(Arrays.toString(arr));
    }
    

    运行结果:

    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    

    实现也非常的简单,首先在外循环里定义了一个index变量存储i的值,这是为了避免重复地比较,因为在每一轮的比较结束后,前i个元素是已经排好序的,所以无需再次比较,只需从i开始即可。后面的比较都是基于index位置的元素进行比较,倘若比较完后index位置的元素是最小值,那就无需交换,不动即可。而如果找到了比index位置的元素更小的元素,那就将该元素的索引赋值给index,然后继续比较,直到比较完成,比较完成之后得到的index即为数组中的最小值,那此时只需要将index位置的元素和i位置的元素交换即可。

    3.插入排序

    插入排序(Insertion sort)是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。
    插入排序的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入到前面已经排序的数组中的适当位置上,直到全部插入完为止。
    演示:
    在这里插入图片描述
    代码如下:

    @Test
    public void InsertionSort() {
    	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	for (int i = 1; i < arr.length; i++) {
    		// 定义待插入的数
    		int insertValue = arr[i];
    		// 找到待插入数的前一个数的下标
    		int insertIndex = i - 1;
    		while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
    			arr[insertIndex + 1] = arr[insertIndex];
    			insertIndex--;
    		}
    		arr[insertIndex + 1] = insertValue;
    	}
    	System.out.println(Arrays.toString(arr));
    }
    

    运行结果:

    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    

    那么在这里,因为数组元素我们并不确定,所以只能将数组的第一个元素看成是一个有序的序列,所以从数组的第二个元素开始才是我们需要去寻找插入位置的元素。所以外层循环从1开始,然后将arr[i],也就是当前的第二个元素先保存起来,然后找到待插入元素的前一个元素下标,也就是i-1,此时通过一个while循环去比较。
    当insertIndex小于0时应该退出循环,因为此时已经与前面的所有元素比较完毕。在比较的过程中,如果待插入元素小于前一个元素,就将前一个元素后移,也就是将前一个元素的值直接赋值给待插入元素位置。因为在最开始已经将待插入元素进行了保存,所以只需将待插入元素的值赋值给它的前一个元素即可。因为在while循环中insertIndex执行了自减操作,所以它的前一个元素下标应为insertIndex + 1。而如果待插入的元素值大于前一个元素,那么就不会进入while循环,这样insertIndex + 1之后的位置仍然是自己所在的位置,所以赋值后值不改变,后面的操作以此类推。

    4.希尔排序

    传统的插入排序算法在某些场景中存在着一些问题,例如[2,3,4,5,1]这样的一个数组,当我们对其进行插入排序的时候,发现要插入的数字是1,而要想将1插入到最前面,需要经过四个步骤,分别将5、4、3、2后移。所以得出结论:如果较小的数是我们需要进行插入的数,那效率就会比较低。鉴于这种场景的缺陷,希尔排序诞生了,它是插入排序的一种更高效的版本。
    先看看希尔排序的概念:
    希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    演示:
    在这里插入图片描述
    动画如果没有看懂,我这里再贴几张静态图:
    在这里插入图片描述
    代码实现:

    @Test
    public void ShellSort() {
    	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    	for (int gap = arr.length / 2; gap > 0; gap /= 2) {
    		// 对数组元素进行分组
    		for (int i = gap; i < arr.length; i++) {
    			// 遍历各组中的元素
    			for (int j = i - gap; j >= 0; j -= gap) {
    				// 交换元素
    				if (arr[j] > arr[j + gap]) {
    					int temp = arr[j];
    					arr[j] = arr[j + gap];
    					arr[j + gap] = temp;
    				}
    			}
    		}
    	}
    
    	System.out.println(Arrays.toString(arr));
    }
    

    运行结果:

    [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    

    那么在上面的程序段中,数组长度为15,所以在第一轮,数组被分为了15 / 2 = 7个小组,然后分别对每个小组的元素进行遍历。在第一轮中小组之间的元素间隔都为7,所以分成的小组数其实也就是元素之间的间隔。接着就可以对每个小组的元素进行比较,然后进行交换,接下来以此类推。

    推荐阅读

    程序员那些必须掌握的排序算法(下)

    展开全文
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧...
    假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。
           3  1  2 5  4  6  9 7  10  8
     
            在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?
     
            给你一个提示吧。请回忆一下冒泡排序,是如何通过“交换”,一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?先别急着往下看,拿出笔来,在纸上画画看。我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小的自恋一下(^o^)。
     

            方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

     
           首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

     

     
     
     

           现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

            6  1  2  5  9 3  4  7  10  8

     
     
     
            到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下。
            6  1  2 5  4  3  9  7 10  8
     
            第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。
            3  1 2  5  4  6  9 7  10  8
     
     

     
     
            到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。
     
            OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3  1 2  5  4”,右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
     
            左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。
     
            如果你模拟的没有错,调整完毕之后的序列的顺序应该是。
            2  1  3  5  4
     
            OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下。
            1  2  3 4  5  6 9  7  10  8
     
            对于序列“9  7  10  8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下。
            1  2  3 4  5  6  7  8 9  10
     
            到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

     
     
            快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。
    #include <stdio.h>
    int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
    void quicksort(int left, int right) {
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要,要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j)//再找右边的
        		i++;       
        	if(i < j)//交换两个数在数组中的位置
        	{
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);//继续处理左边的,这里是一个递归的过程
        quicksort(i+1, right);//继续处理右边的 ,这里是一个递归的过程
    }
    int main() {
    	int i;
        //读入数据
    	scanf("%d", &n);
    	for(i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
        quicksort(1, n); //快速排序调用
        //输出排序后的结果
        for(i = 1; i < n; i++)
        	printf("%d ", a[i]);
        printf("%d\n", a[n]);
        return 0;
    }

     

     
    展开全文
  • 冒泡排序

    万次阅读 多人点赞 2019-09-16 16:28:32
    冒泡排序是一种比较简单的排序算法,它循环走过需要排序的元素,依次比较相邻的两个元素,如果顺序错误就交换,直至没有元素交换,完成排序。 若对n个人进行排序,我们需要n-1次比较,所以第k次比较需要进行n-k次...
  • 排序

    万次阅读 2020-01-07 19:58:34
    记录一下几种排序: 桶排序排序:例如需要排序数的范围是0~n,那你则需要申请n+1一个变量,也就是说要写成int a[n+1]。应为我们需要用n+1个“桶”来存储0~n每一个数出现的次数。 即便只给你5个数进行排序(例如这...
  • 快速排序

    万次阅读 多人点赞 2017-03-18 18:11:48
    快速排序
  • 冒泡排序、冒泡排序动画、冒泡排序代码、冒泡排序教程 代码下载
  • 算法学习总结(2)——温故十大经典排序算法

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

    万次阅读 多人点赞 2017-07-27 21:35:06
    最近在刷ACM经常用到排序,以前老是写冒泡,可把冒泡带到OJ里后发现经常超时,所以本想用快排,可是很多学长推荐用sort函数,因为自己写的快排写不好真的没有sort快,所以毅然决然选择sort函数 用法 1、sort函数...
  • JS排序算法:冒泡法、快速排序法、选择排序法、插入排序法、哈希排序//生成数组 var arr = new Array(1000); for (var i = 0; i ; i++) { arr[i] = (Math.round(Math.random() * 1000)); }1.冒泡法 排序思想:...
  • Python杂谈 | (1)Python列表合并、去重和排序

    万次阅读 多人点赞 2018-10-13 14:10:27
    列表排序 一.列表合并--append() 1.列表对象的append()可以将元素追加到列表中。 2.列表对象的append()可以将另一个列表追加到当前列表中,作为当前列表的一个元素。 二.列表合并--extend() 与append()不同...
  • 白话经典算法系列之六 快速排序 快速搞定

    万次阅读 多人点赞 2011-08-13 17:19:58
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
  • 快速排序---(面试碰到过好几次)

    万次阅读 多人点赞 2018-09-10 12:20:21
       快速排序,说白了就是给基准数据找其正确索引位置的过程.    如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示...
  • 希尔排序--简单易懂图解

    万次阅读 多人点赞 2018-04-19 15:56:22
    图解算法---希尔排序前情回顾:直接插入排序(对插入排序不熟悉的建议先阅读此文)一天,一尘拿着扑克自己在那玩,刚被师傅看见了首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行...
  • using Microsoft.AspNetCore.Builder; using Microsoft.Extensions.DependencyInjection; using Microsoft.Extensions.Hosting; using Microsoft.OpenApi.Models; using Volo.Abp; using Volo.Abp.AspNetCore.Mvc;...
  • 排序算法(1)选择排序

    千次阅读 2017-09-20 16:39:55
    排序算法(1)选择排序法 原理 举例 程序范例 原理选择排序法属于排序算法中常见的也是大家最容易理解的排序算法,可以作为排序算法的入门来学习。 那么选择排序法的原理是什么呢?选择排序就是当n个数字需要由大到...
  • using Microsoft.AspNetCore.Builder; using Microsoft.Extensions.DependencyInjection; using Microsoft.Extensions.Hosting; using Microsoft.OpenApi.Models; using Volo.Abp; using Volo.Abp.AspNetCore.Mvc;...
  • using Microsoft.AspNetCore.Builder; using Microsoft.Extensions.DependencyInjection; using Microsoft.Extensions.Hosting; using Microsoft.OpenApi.Models; using Volo.Abp; using Volo.Abp.AspNetCore.Mvc;...
  • 实现集合List中的元素进行排序

    万次阅读 多人点赞 2016-06-14 22:08:32
    Collections对List集合中的数据进行排序 有时候需要对集合中的元素按照一定的规则进行排序,这就需要用到 Java中提供的对集合进行操作的工具类Collections,其中的sort方法 先看一个简单的例子: public static ...
  • java排序算法总结

    千次阅读 多人点赞 2019-04-19 12:30:20
    java排序算法总结 排序,这是一个很古老但是又很经典的问题,世界上有很多中优秀排序算法的实现,在这里,我总结了其他比较常用的几种排序算法 1.java排序算法一览 冒泡排序和基数排序排序和计数排序 归并排序和...
  • Java二维数组排序

    千次阅读 2019-06-29 15:46:12
    Java二维数组排序
  • 快速排序基本思路(通俗易懂+例子)

    万次阅读 多人点赞 2017-07-02 22:06:32
    快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单 下面进行简单的试试快速排序的基本思想是 1、先从数列中取出一个数作为基准数 2、分区过程,将比这个数大的数全放到它的...
  • python-列表元素绝对值排序

    万次阅读 2018-12-21 13:13:59
    列表元素绝对值排序(10分) 题目内容: 输入一个列表,要求列表中的每个元素都为整数; 将列表中的所有元素按照它们的绝对值大小进行排序,绝对值相同的还保持原来的相对位置,打印排序后的列表(绝对值大小仅...
  • 理解希尔排序排序过程

    万次阅读 多人点赞 2018-01-30 09:41:06
    1,有关插入排序 (1)插入排序的基本方法是:每步将一个待排序的元素,按其排序码大小插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。 (2)可以选择不同的方法在已经排好序的有序数据表...
  • Java基础(冒泡排序)

    万次阅读 多人点赞 2019-05-17 16:54:30
    冒泡排序简介 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有的元素重复以上的...
  • MongoDB中的排序规则

    万次阅读 2020-05-31 00:58:15
    $min $max类型不一样时会按照如下的类型判断大小值 最小 Null Number (ints , longs , doubles , decimals) Symbol , String Object Array BinData ObjectId Boolean Date ...最大 Regular Expression
  • Python列表排序 list.sort方法和内置函数sorted

    千次阅读 多人点赞 2019-05-18 15:17:54
    Python列表排序 list.sort方法和内置函数sorted 很多时候我们获取到一个列表后,这个列表并不满足我们的需求,我们需要的是一个有特殊顺序的列表. 这时候就可以使用list.sort方法和内置函数sorted,本文就是介绍list....
  • 归并排序 详解

    万次阅读 多人点赞 2018-05-30 13:38:53
    也许有很多同学说,原来也学过很多O(n^2)或者O(n^3)的排序算法,有的可能优化一下能到O(n)的时间复杂度,但是在计算机中都是很快的执行完了,没有看出来算法优化的步骤,那么我想说有可能是你当时使用的测试...

空空如也

1 2 3 4 5 ... 20
收藏数 671,398
精华内容 268,559
热门标签
关键字:

排序