穩(wěn)定性的定義

假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

1.選擇排序

選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元素選擇第二小的，依次類推，直到第n - 1個(gè)元素，第n個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。

void selectionsort(vector<int>arr,int size)
{
    int i,j,min;
    i=0;
    j=0;
    min=0;
    for(i=0;i<size;i++)
    {
        int tmp=arr[min];
        for(j=i+1;j<size;j++)
        {
            if(arr[j]<arr[min])
                min=j;
        }
        swap(arr[min],arr[i]);
    }
}

2.堆排序

void percdown(vector<int>a,int i,int n)
{
    int child;//孩子節(jié)點(diǎn)
    int parent;
    int tmp=a[i];//臨時(shí)變量
    for(parent=i;parent*2+1<n;parent=child)
    {
        child=parent*2+1;//當(dāng)前節(jié)點(diǎn)的左孩子節(jié)點(diǎn)
        //比較左右孩子誰(shuí)大
        if(child!=n-1 && a[child]<a[child+1])//若存在右子節(jié)點(diǎn)且右子節(jié)點(diǎn)更大
            child++;
        if(tmp<a[child])
            a[parent]=a[child];//下濾
        else
            break;//找到合適節(jié)點(diǎn)
    }
    a[i]=tmp;
}
void heapsort(vector<int>a,int n)
{
    int i;
    //初始化堆
    for(i=n/2;i>=0;i--)
    {
        percdown(a,i,n);
    }
    //排序
    for(i=n-1;i>0;i--)
    {
        swap(a[0],a[i]);
        percdown(a,0,i);
    }

3.插入排序

插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。

//插入排序
void insertionsort(vector<int>arr,int size)
{
    int i,j,tmp;
    for(i=1;i<size;i++)
    {
        tmp=arr[i];
        for(j=i;j>0&&arr[j-1]>tmp;j--)
            arr[j]=arr[j-1];//挪位置
        arr[j]=tmp;
    }
}

4.希爾排序

希爾排序就是插入排序的進(jìn)階。每次選擇一個(gè)步長(zhǎng)進(jìn)行插入排序

void shellsort(vector<int>arr,int size)
{
    int i,j,gap,tmp;
    for(gap=size/2;gap>0;gap/=2)
    {
        for(i=gap;i<size;i++)
        {
            tmp=arr[i];
            for(j=i;j>0&&arr[j-gap]>tmp;j-=gap)
                arr[j]=arr[j-gap];
            arr[j]=tmp;
        }
    }
}

5.冒泡排序

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。

void bubblesort(vector<int>arr,int size)
{
    int i,j;
    for(i=0;i<size;i++)
    {
        for(j=0;j<size-i;j++)
        {
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
        }
    }
}

6.快速排序

//三路快排
int median3(vector<int>arr,int left,int right)
{
    int center=(right+left)/2;
    if(arr[left]>arr[center])
        swap(arr[left],arr[center]);
    if(arr[left]>arr[right])
        swap(arr[left],arr[right);
    if(arr[center]>arr[right])
        swap(arr[center],arr[right]);
    swap(arr[center],arr[right-1]);
    return arr[right-1];
}

void quicksort(vector<int>arr,int left,int right)
{
    int center=median3(arr,left,right);
    int i=left;
    int j=right;
    while(i!=j){
        while(arr[i]<arr[center] && i<j)
            i++;
        while(arr[j]>arr[center] && i<j)
            j--;
        if(i<j)
            swap(arr[i],arr[j]);
        else break;
    }
    swap(arr[i],arr[right]-1);
    quicksort(arr,left,i-1);
    quicksort(arr,i+1,right);
}

8.歸并排序

//歸并排序
void merge(vector<int>&arr,int left,int mid,int right)
{
    vector<int> res;
    int len=right-left+1;
    int i=left;
    int j=mid+1;
    int index=0;
    while(i<=mid && j<=right)
    {
        res[index++] =(arr[i]<=arr[j])? arr[i++] : arr[j++];
    }
    while(i<=mid)
        res[index++]=arr[i++];
    while(j<=right)
        res[index++]=arr[j++];
    for(int k=0;k<len;k++)
        arr[left++]=res[k++];
}


void mergesort(vector<int>&arr,int len)
{
    if(left == right)
        return ;
    int mid=(left+right)/2;
    merge(arr,left,mid);
    merge(arr,mid+1,right);
    merge(arr,left,mid,right);

}

穩(wěn)定性的意義
如果只是簡(jiǎn)單的進(jìn)行數(shù)字的排序，那么穩(wěn)定性將毫無(wú)意義。
如果排序的內(nèi)容僅僅是一個(gè)復(fù)雜對(duì)象的某一個(gè)數(shù)字屬性，那么穩(wěn)定性依舊將毫無(wú)意義
如果要排序的內(nèi)容是一個(gè)復(fù)雜對(duì)象的多個(gè)數(shù)字屬性，但是其原本的初始順序毫無(wú)意義，那么穩(wěn)定性依舊將毫無(wú)意義。
除非要排序的內(nèi)容是一個(gè)復(fù)雜對(duì)象的多個(gè)數(shù)字屬性，且其原本的初始順序存在意義，那么我們需要在二次排序的基礎(chǔ)上保持原有排序的意義，才需要使用到穩(wěn)定性的算法，例如要排序的內(nèi)容是一組原本按照價(jià)格高低排序的對(duì)象，如今需要按照銷量高低排序，使用穩(wěn)定性算法，可以使得想同銷量的對(duì)象依舊保持著價(jià)格高低的排序展現(xiàn)，只有銷量不同的才會(huì)重新排序。（當(dāng)然，如果需求不需要保持初始的排序意義，那么使用穩(wěn)定性算法依舊將毫無(wú)意義）。