排序问题（蛮力法，分治法）

布满荆棘的人生 2022-04-16 04:59 235阅读 0赞

### **蛮力法：** ###

**选择排序法：**

算法思想：在剩余序列中选出最小（或最大）的关键字，和剩余序列的第一个关键字交换位置，依次选择下去（每次扫描结束找出最小的一个元素依次放在前面的位置），直至使整个序列有序。

代码实习：

#include<iostream>
    using namespace std;
    void print(int a[], int n)
    
    {  
        for(int j= 0; j<n; j++)
    	{  
            cout<<a[j] <<"  ";  
        }  
        cout<<endl;  
    }
    
    void selectSort(int a[], int len)
    {
    	int minindex, temp;
    	for(int i = 0; i<len-1;i++)
    	{
    	    minindex = i;
    	    for(int j = i+1; j<len; j++)
    		{
    		    if(a[j]<a[minindex])
    		    minindex = j;		
    		}
    		temp = a[i];
    		a[i] = a[minindex];
    		a[minindex] = temp;
    	}
    }
    
    int main()
    {  
        int a[10] = {8,1,9,7,2,4,5,6,10,3};  
        cout<<"初始序列：";  
        print(a,10);  
        selectSort(a,10);  
        cout<<"排序结果：";  
        print(a,10);  
        system("pause"); 
    }

算法分析：

算法中两层循环的执行次数和初始序列没有关系，第二层循环每一次都需要遍历剩余带排序序列，故时间复杂度为O(n^2)。

**冒泡排序法：**

算法思想：

冒泡排序法每次是将相邻两个元素进行比较，将较大（小）的元素放在后面，这样一次扫描结束后就将当前最大（小）的那个元素放在了列表的后面。

代码实现：

/*①传统的冒泡排序法sort_Bubble：内外两轮循环，前后两个数据依次比较； 
    ②改进的冒泡排序法sort_Bubble2：同样是内外两次循环，但用一个标记来标
    识当前这一轮是否发生数据交换，如果没发生，说明排序实际上已经完成，可
    以提前结束排序任务。*/
    void swap(int*a , int* b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    void sort_Bubble(int arr[],int N)
    {
        /// step用于统计比较次数
        int step = 0;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N-i-1;j++)
            {
                step++;
                if(arr[j]>arr[j+1])
                    swap(arr+j,arr+j+1);
            }
        }
        cout<<"sort_Bubble:"<<step<<endl;
    }
    
    void sort_Bubble2(int arr[],int N)
    {
        /// step用于统计比较次数
        int step = 0;
        bool changeFlag = true;
        for(int i=0;i<N;i++)
        {
            if(changeFlag == false)
                break;
            changeFlag = false;
            for(int j=0;j<N-i-1;j++)
            {
                step++;
                if(arr[j]>arr[j+1])
                {
                    swap(arr+j,arr+j+1);
                    changeFlag = true;
                }
            }
        }
        cout<<"sort_Bubble2:"<<step<<endl;
    }
    
    int main()
    {
        int tmpArray[10] = {0,-3,12,234,9,45,99,123,401,990};
        int tmpArray2[10] = {0,-3,12,234,9,45,99,123,401,990};
        for(int i=0;i<10;i++)
            cout<<tmpArray[i]<<"\t";
        cout<<"\n冒泡排序法："<<endl;
        sort_Bubble(tmpArray,10);
        sort_Bubble2(tmpArray2,10);
        for(int i=0;i<10;i++)
            cout<<tmpArray[i]<<"\t";
        return 0;
    }

算法分析：

O(n^2).

### **分治法：** ###

将一个难以解决的大问题，划分成一些规模较小的子问题，从而得到原问题的解。

一般来说，分治法由以下三步组成：

1）划分：把规模为n的原问题划分为k个规模较小的子问题

2）求解子问题：各个子问题的解法与原问题的解法通常是相同的，可以**用递归方法求解各个子问题**，有时递归问题也可以用循环来实现。

3）合并：把各个子问题的解合并起来，合并的代价因情况的不同而有很大差异，分治算法的效率很大程度上依赖于合并的实现。

**归并排序法：**

算法描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpX3l1ZQ_size_16_color_FFFFFF_t_70][]

算法实现：

#include<iostream>
    using namespace std;
    const int maxn=500000,INF=0x3f3f3f3f;
    int L[maxn/2+2],R[maxn/2+2];
    void merge(int a[],int n,int left,int mid,int right)
    {
        int n1=mid-left,n2=right-mid;
        for(int i=0;i<n1;i++)
            L[i]=a[left+i];
        for(int i=0;i<n2;i++)
            R[i]=a[mid+i];
        L[n1]=R[n2]=INF;
        int i=0,j=0;
        for(int k=left;k<right;k++)
        {
            if(L[i]<=R[j])
                a[k]=L[i++];
            else
                a[k]=R[j++];
        }
    }
    void mergesort(int a[],int n,int left,int right)
    {
        if(left+1<right)
        {
            int mid=(left+right)/2;
            mergesort(a,n,left,mid);
            mergesort(a,n,mid,right);
            merge(a,n,left,mid,right);
        }
    }
    int main()
    {
        int a[maxn],n;
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        mergesort(a,n,0,n);
        for(int i=0;i<n;i++)
        {
            if(i)
                cout<<" ";
            cout<<a[i];
        }
        cout<<endl;
        return 0;
    }

算法分析：

归并排序算法采用的是分治算法,即把两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.一般来说，n个数据大致会分为logN层，每层执行merge的总复杂度为O(n)， 所以总的复杂度为O(nlogn)。

**快速排序法：**

算法描述：

快速排序首先选一个轴值(pivot，也有叫基准的)，将待排序记录划分成独立的两部分，左侧的元素均小于轴值，右侧的元素均大于或等于轴值，然后对这两部分再重复，直到整个序列有序。过程是和二叉搜索树相似，就是一个递归的过程

算法实现：

排序函数：

QuickSort(int arr[], int first, int end){
     if (first < end) {
       int pivot = OnceSort(arr,first,end);
       //已经有轴值了，再对轴值左右进行递归
       QuickSort(arr,first,pivot-1);
       QuickSort(arr,pivot+1,end);
    　}
    }

一次排序的函数：

int OnceSort(int arr[], int first, int end){
     int i = first,j = end;
     //当i<j即移动的点还没到中间时循环
     while(i < j){
      //右边区开始，保证i<j并且arr[i]小于或者等于arr[j]的时候就向左遍历
      while(i < j && arr[i] <= arr[j]) --j;
      //这时候已经跳出循环，说明j>i 或者 arr[i]大于arr[j]了，如果i<j那就是arr[i]大于arr[j]，那就交换
      if(i < j){
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
      }
      //对另一边执行同样的操作
      while(i < j && arr[i] <= arr[j]) ++i;
      if(i < j){
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
      }
     }
     //返回已经移动的一边当做下次排序的轴值
     return i;
    }

算法分析：

快速排序时间复杂度的最好情况和平均情况一样为O(nlog2 n)，最坏情况下为O(n^2 )，这个看起来比前面两种排序都要好，但是这是不稳定的算法，并且空间复杂度高一点（ O(nlog2 n)，而且快速排序适用于元素多的情况。

发现一个超详细的排序总结[https://www.cnblogs.com/zyb428/p/5673738.html][https_www.cnblogs.com_zyb428_p_5673738.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpX3l1ZQ_size_16_color_FFFFFF_t_70]: /images/20220416/f053ee51ebae4c32b7c3c3024c90070a.png
[https_www.cnblogs.com_zyb428_p_5673738.html]: https://www.cnblogs.com/zyb428/p/5673738.html