注册登录

快速排序，插入排序，冒泡排序，归并排序

快速排序：O(n2）

真正正确的快速排序：
#include<iostream>
#include<cstdio>
using namespace std;
int a[100];
/*void swap(int a,int b){
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}*/
void quicksort(int left,int right){
    int i,j,t;
    if(left>right)
        return;
    int temp=a[left];
    i=left;
    j=right;
    while(i<j){
        while(a[j]>temp&&i<j)
            j--;
        a[i]=a[j];
        while(a[i]<temp&&i<j)
            i++;
        a[j]=a[i];
    }
    a[i]=temp;
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int main(){
    int num;
    cin>>num;
    for(int i=1;i<=num;i++)
    scanf_s("%d",&a[i]);
    quicksort(1,num);
    for(int i=1;i<=num;i++)
        cout<<a[i]<<endl;
    return 0;
}
知识兔

插入排序: O(n2)

include<iostream>
#include<cstdio>
using namespace std;
int a[100];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){//i指要进行比较的第几个数
        if(a[i]<a[i-1]){
            int j=i-1;
            int x=a[i];
            while(j>=0&&a[j]>x){
                a[j+1]=a[j];//发现前数字大于后面数字的情况
                      将后面的数字进行后移。
                j--;
            }
            a[j+1]=x;//将进行比较的数插入
        }
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<endl;
    return 0;
}
知识兔

 归并排序：O(nlogn)


#include <vector> 
using namespace std;
void merge(vector<int> &arr,int L,int mid,int R){
    int *help = new int(R-L+1);    
    int p1=L,p2=mid+1,i=0;    
    while(p1<=mid && p2<=R)    {    
        help[i++] = arr[p1]>arr[p2] ? arr[p2++] : arr[p1++];
    }    
    while(p1<=mid)    
        help[i++] = arr[p1++];    
    while(p2<=R)    
        help[i++] = arr[p2++]; 
    for (int i=0;i<R-L+1;i++)    
    {        
        arr[L+i] = help[i];
    }
}
void sortprocess(vector<int> &arr,int L,int R)
{    if (L < R)    {    
    int mid = L + ((R-L)>>2);  //  (L+R)/2    
    sortprocess(arr,L,mid);    
    sortprocess(arr,mid+1,R);    
    merge(arr,L,mid,R);    }}
void MergeSort(vector<int> &arr,int L,int R){
    if (arr.size()<2)    
        return;    sortprocess(arr,L,R);} 
int main(){    
    vector<int> arr;    
    int n,temp;    cin>>n;  //输入n个数    
    for (int i=0;i<n;i++)    
    {    
        cin>>temp;  //输入数据    
        arr.push_back(temp);    
    }     
    MergeSort(arr,0,arr.size()-1); 
    for(int i=0;i<arr.size();i++)    
        cout<<arr[i]<<endl; 
    system("pause");    
    return 0;
}
知识兔
计算机