lalalala


私信TA

用户名:zhangshuo

访问量:109419

签 名:

像狗一样的学习,像绅士一样地玩耍。

等  级
排  名 4
经  验 24289
参赛次数 10
文章发表 201
年  龄 12
在职情况 学生
学  校 芜湖市第十一中学
专  业

  自我简介:

今日懒惰流下的口水,将会成为明日里伤心的泪水。

解题思路:

多种排序详解

注意事项:

参考代码:

1.插排

//直接插入排序是一种最简单的排序方法,
//它的基本操作是将一个记录插入到已经排好序的有序表中,
//从而得到一个新的且记录数增加了1的有序表。
#include <iostream>
#include <iomanip>
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
using namespace std;
  void swap(int &x, int &y)
  {
     int temp = x;
      x = y;
       y = temp;
  }
   void insertion(int a[], int sz)
    {
      for(int i=1;i<=sz;i++) {
       int j=i;
        while(j>0&&(a[j]<a[j-1])) {
          swap(a[j],a[j-1]);
           j--;
        }
    }
}
   int main()
     {
       int a[10005],n;
         scanf("%d",&n);
           for(int i=1;i<=n;i++)
             scanf("%d",&a[i]);
               insertion(a,n);
    for(int i=1;i<=n;i++)
     {
        printf("%d ",a[i]);
	 } 
}


2.归排

//归并排序是基于归并操作完成的,
//而一次归并操作是通过两个或两个以上的有序表
//合并成一个新的有序表完成的。
//常见的归并排序是2-路归并排序,
//其核心操作是将一维数组中前后相邻的两个有序序列
//归并成一个有序序列。 
#include<iostream>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
using namespace std;
 const int SIZE = 100;
  int arr[SIZE];
   int rec[SIZE];
     void merge(int fir,int end,int mid);
       int pass(int n);
         void mergeSort3(int n);
           void mergeSort3(int n){
             int num=pass(n);
    while(num!=2)
	{
        for(int i=0;i<num;i+=2)
            merge(rec[i],rec[i+2]-1,rec[i+1]-1);
        num=pass(n);
    }
}
void merge(int fir,int end,int mid){
    int tempArr[SIZE];
      int fir1=fir,fir2=mid+1;
        for(int i=fir;i<=end;i++){
          if(fir1>mid)
            tempArr[i]=arr[fir2++];
        else if(fir2>end)
            tempArr[i]=arr[fir1++];
        else if(arr[fir1]>arr[fir2])
            tempArr[i]=arr[fir2++];
        else 
            tempArr[i]=arr[fir1++];
    }
    for(int i=fir;i<=end;i++)
        arr[i]=tempArr[i];
}
int pass(int n){
     int num=0;
      int biger=arr[0];
       rec[num++]=0;
        for(int i=1;i<n;i++){
          if(arr[i]>=biger)biger=arr[i];
        else 
		{
            rec[num++]=i;
            biger=arr[i];
        }
    }
     rec[num++]=n;
    return num;
}
int main(){
     int n;
   	  cin>>n;
        for(int i=0;i<n;i++)cin>>arr[i];
         mergeSort3(n);
          for(int i=0;i<n;i++)cout<<arr[i]<<" ";
           cout<<endl;
}


3.快排

//快速排序是对起泡排序的一种改进。
//它的基本思想是,
//通过一趟排序将待排序的记录分割成两个独立的部分,
//其中一部分记录的关键字均比另一部分的关键字小,
//在分成两个部分之后则可以分别对这两个部分继续进行排序,
//从而使整个序列有序。
#include <cstdio>
#include <algorithm>
#include <queue>//头文件
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大(或最小)的元素,导致每次只划分出了一个分区,需要进行n-1次划分才能结束递归,时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数,这样每次都均匀的划分出两个分区,只需要logn次划分就能结束递归,时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量),取决于递归树的深度,一般为O(logn),最差为O(n)       
// 稳定性 ---------- 不稳定
using namespace std;
const int maxx = 100000 + 10;
int Heap[maxx];
int main()
{
    int n,num = 0,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),Heap[++num]=x,push_heap(Heap+1,Heap+num+1,greater<int>());
    for(int i=1;i<=n;i++)
            printf("%d ",Heap[1]),pop_heap(Heap+1,Heap+num+1,greater<int>()),num--;
            return 0;
}


4.选排

//选择排序的基本思想是:
//每一趟比较过程中,
//在n-i+1(i=1,2,...,n-1)
//个记录中选取关键字最小的记录作为有序序列中的第i个记录。
//在多种选择排序中,
//最常用且形式最为简单的是简单选择排序。
#include<cstdio>
#include<iostream>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
using namespace std;
int main()
{
	int n;
	 scanf("%d",&n);
	   int a[10005];
	     for(int i=1;i<=n;i++)
	        {
		      scanf("%d",&a[i]);
	        }
	     for(int i=1;i<n;i++)
            {
              int min=i;
               for (int j=i+1;j<n+1;j++)
                   {
                      if(a[j]<a[min])
                       min=j;
                   }
                swap(a[i],a[min]);
            }
	    for(int i=1;i<=n;i++)
	        printf("%d ",a[i]);  
}


 

0.0分

8 人评分

  评论区

push_heap
pop_heap
是什么不太懂
什么书有深入的
2020-05-27 17:16:19 | |
#include<iostream>
using namespace std;

void sort(int arr[])//冒泡排序 
{
	int temp;
	for(int i=0;i<10;i++)
	{
		for(int j=i+1;j<10;j++)      
		{
			if(arr[j]<arr[i])
			{
				temp=arr[j];
				arr[j]=arr[i];
				arr[i]=temp;
			}
		}
	}
}
int main()
{
	int arr[10];
	int x;
	for(int i=0;i<10;i++)
	{
		cin>>x;
		arr[i]=x;
	}
	sort(arr);
	for(int i=0;i<10;i++)
	{
		cout<<arr[i]<<endl;
	}
	return 0;
}
2020-03-02 21:54:46 | |
不过为啥这道选择排序题,那么多人不用选择排序??这篇题解选择排序也是最后一个,应该第一个,别的方法只等算扩展资料。
2020-02-29 16:58:56 | |
  • «
  • 1
  • »