基于排序算法的特性划分的排序

叁歲伎倆 2021-09-21 17:08 323阅读 0赞

> ### **一.基于排序算法的特性，大概可分为以下三种** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70][]

> ### 二.例题 ###

1.线性排序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 1][]

**输入 ：**

5 3

1 -4 6 -3 5

**输出：**

6 5 1

**分析题目：****基于比较****的排序的算法f时间复杂度为O（nlogn),****给定范围的****线性排序需要O（n）；**

**本题元素给定了范围，所有的值都在\[-500000,500000\]，则本题可通过线性排序来实现。****以后做题时需注意排序的数据是否有范围哦！**

代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstring> 
    
    using namespace std;
    
    const int MAXN = 1e6 + 10;
    const int RANGE = 5e5;
    
    int arr[MAXN];
    int number[MAXN];
    int main(){
    	int n,m;
    	while(scanf("%d%d",&n,&m)!=EOF){
    		//清空数组中的数据,以防上次的数据残留 
    		memset(number,0,sizeof(number)) ;
    		//输入一组数 
    		for(int i = 0; i < n; ++i){
    			scanf("%d",&arr[i]);
                //数组下标是从0开始，所以这里每个数据+500000，则可以保证最小的数为0
    			number[arr[i]+RANGE]++;
    		}
    		//处理数据 
    		int index = 0;
    		for(int i = 0; i < MAXN; ++i){
    			while(number[i]--){
                    //恢复成它原来输入的数据
    				arr[index++] = i - RANGE;
    			}
    		}
    		//输出数据 
    		for(int i = n-1;i >= n-m;--i){
    			if(i==n-m){
    				printf("%d\n",arr[i]);
    			}else{
    				printf("%d ",arr[i]);
    			}
    		} 
    	}
    	return 0;
    }

2.逆序数对

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 2][]

**输入：**

4 2 8 0 3

10 0 1 2 3 4 5 6 7 8 9

6 -42 23 6 28 -100 65537

5 0 0 0 0 0

**输出：（用的devc++,输出就是这样）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 3][]

分析：理解归并排序是重点！！！

下面是动态图：

![2f9f62d486be19b87a3f37f13eb75786.png][]

**代码如下：**

#include<iostream>
    #include<cstdio>
    
    using namespace std;
    
    const int MAXN=1010; 
    
    int arr[MAXN];
    int temp[MAXN];
    int number;
    //合并 
    void Combine(int left,int middle,int right){
    	int i = left;
    	int j = middle + 1;
    	int k = left;
    	while(i <= middle && j <= right){
    		if(arr[i] <= arr[j]){
    			temp[k++] = arr[i++];
    		}else{
    			//求逆序对的数目 
    			number += middle-i+1;
    			temp[k++] = arr[j++];
    		}
    	}
    	//处理左边和右边剩余的数据 
    	while(i <= middle){
    		temp[k++] = arr[i++];
    	}
    	while(j <= right){
    		temp[k++] = arr[j++];
    	}
    	for(k = left; k <= right; ++k) {
    		arr[k] = temp[k];
    	}
    	return;
    } 
    //排序 
    void MergeSort(int left,int right){
    	if(left < right){
    		//这种写法容易导致溢出当left和right都比较接近整型上界时 
    		//int middle = (left+right) / 2;
    		int middle = left + (right - left) / 2;
    		MergeSort(left, middle);
    		MergeSort(middle + 1, right);
    		Combine(left, middle, right);
    	}
    	return;
    }
    int main(){
    
    	int caseNumber;
    	scanf("%d",&caseNumber);
    	for(int current = 1; current <= caseNumber; ++current){
    		int n;
    	    scanf("%d",&n);
        	for(int i = 0; i<n; ++i){
    		   scanf("%d",&arr[i]);
        	} 
        	number = 0;
        	//进行归并排序 
    	    MergeSort(0,n-1);
    	    printf("Scenario #%d:\n",current);
    	    //输出逆序对的数目 
        	printf("%d\n\n",number);
    	}
    	return 0;
    }

3.第K大数

主要运用了快速排序的思想！

下面来看一下快速排序的动态图，有助于更好的理解。

![eaca66d26efe27519e8c462d3a7d4593.png][]

下面是求第K大数的代码:

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    
    using namespace std;
    
    int arr[100];
    
    int Partition(int left, int right){
    	//生成一个（在左和右之间）随机值 ，即中心值 
    	int random = left + rand() % (right - left);
    	//交换最左端的和随机值 
    	swap(arr[left], arr[random]); 
    	//循环，把大的放到右边，把小的放在中心值得左边 
    	while(left < right){
    		//当左边的值小于等于右边的值时，右指针左移 
    		while(left < right && arr[left] <= arr[right]){
    			--right;
    		}
    		//直到不能移动时，即左边的值大于右边的，则交换 ，此时中心值在右边 
    		swap(arr[left], arr[right]);
    	    //当左边的值小于等于右边的值时，左指针右移 
    		while(left < right && arr[left] <=arr[right]){
    			++left;
    		}
    		//直到不能移动时，即左边的值大于右边的，则交换
    		swap(arr[left], arr[right]);
    	}
    	//最后左指针和右指针指向同一个地方 
    	return left;
    }
    
    int QuickSort(int left, int right, int k){
    	if(left < right){
    		int position = Partition(left, right);
    		//比较位置，确定找的范围 
    		if (position == k - 1){
    		    return arr[position];	
    		} else if (position < k - 1){
    			return QuickSort(position + 1,right,k);
    		} else {
    			return QuickSort(left,position - 1,k);
    		}
    	
    	}
    }
    
    
    int main(){
    	//输入数据 
    	int n;
    	scanf("%d",&n);
    	for(int i = 0; i < n; ++i){
    		scanf("%d",&arr[i]);
    	}
    	//获取第K大的数 
    	int k;
    	scanf("%d",&k);
    	//输出结果 
        printf("%d\n",QuickSort(0,n-1,k));
    	return 0; 
    }

附十大经典排序算法动态图和代码链接：[https://www.cnblogs.com/onepixel/articles/7674659.html][https_www.cnblogs.com_onepixel_articles_7674659.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70]: /images/20210920/fe69e5a38ead491cb98a52917979c8bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 1]: /images/20210920/b49304ddab264e00b2f1e0a6f6aac3da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 2]: /images/20210920/26bbd249b1a64d7c9a783b6d7cb57afb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjc5ODE4_size_16_color_FFFFFF_t_70 3]: /images/20210920/b6ea6168dcd7444abd4532847ff33cc6.png
[2f9f62d486be19b87a3f37f13eb75786.png]: /images/20210920/692db8e852814c1280114f14d1787e1b.png
[eaca66d26efe27519e8c462d3a7d4593.png]: /images/20210920/7790f0415d3e494f80096750fc0c0f15.png
[https_www.cnblogs.com_onepixel_articles_7674659.html]: https://www.cnblogs.com/onepixel/articles/7674659.html