天天看點
傳回

排序操作的學習排序操作的學習

排序操作的學習

一、排序的簡述

  • 排序是計算機内經常進行的一種操作，其目的是将一組**“無序”的記錄序列調整為“有序”**的記錄序列。分内部排序和外部排序，若整個排序過程不需要通路外存便能完成，則稱此類排序問題為内部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在記憶體中完成，則稱此類排序問題為外部排序。内部排序的過程是一個逐漸擴大記錄的有序序列長度的過程。
  • 主要分類：
排序操作的學習排序操作的學習
排序操作的學習排序操作的學習
  • 比較和非比較的差別：常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序**。在排序的最終結果裡，元素之間的次序依賴于它們之間的比較。每個數都必須和其他數進行比較，才能确定自己的位置。在冒泡排序之類的排序中，問題規模為n，又因為需要比較n次，是以平均時間複雜度為O(n²)。在歸并排序、快速排序之類的排序中，問題規模通過分治法消減為logN次，是以時間複雜度平均O(nlogn)。比較排序的優勢是，适用于各種規模的資料，也不在乎資料的分布，都能進行排序。可以說，比較排序适用于一切需要排序的情況。計數排序、基數排序、桶排序則屬于非比較排序。非比較排序是通過确定每個元素之前，應該有多少個元素來排序。針對數組arr，計算arr[i]之前有多少個元素，則唯一确定了arr[i]在排序後數組中的位置。非比較排序隻要确定每個元素之前的已有的元素個數即可，所有一次周遊即可解決。算法時間複雜度O(n)。非比較排序時間複雜度底，但由于非比較排序需要占用空間來确定唯一位置。是以對資料規模和資料分布有一定的要求。

二、主要排序的C語言實作

1.冒泡排序（Bubble Sort）

​ 冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一 次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

排序操作的學習排序操作的學習
//冒泡排序
void BubbleSort(int a[], int n)
{
    int i, j;
    for(i=0; i<n; i++){
        bool flag=false;              //表示本趟冒泡是否發生交換的标志
        for(j=1; j<n-i; j++){         //j的起始位置為1，終止位置為n-i  
            if(a[j]<a[j-1]){
               Swap(a[j-1], a[j]);
                flag=true;
            }
        }
        if(flag==false)             //未交換，說明已經有序，停止排序
            return;
    }          
}

最佳情況：T(n) = O(n) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

2.選擇排序（Selection Sort）

表現最穩定的排序算法之一，因為無論什麼資料進去都是O(n2)的時間複雜度，是以用到它的時候，資料規模越小越好。唯一的好處可能就是不占用額外的記憶體空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。選擇排序(Selection-sort)是一種簡單直覺的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

排序操作的學習排序操作的學習
//選擇排序,以升序為例
void SelectSort(int a[],int n){
    int i,j,min;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++){
            if(a[j]<a[min)
                      min=j;
        }
        if(min!=i)
		   Swap(a[i],a[min]); 
    }
}
void Swap(int a,int b){
	int temp;
    temp=a;
    a=b;
    b=temp;
}

最佳情況：T(n) = O(n2) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

3.插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

排序操作的學習排序操作的學習
//直接插入法一
void InsertSort1(int a[], int n)
{
    int i, j;
    for(i=1; i<n; i++)
        if(a[i] < a[i-1])   
        {
            int temp = a[i];                       //儲存要比較的值
            for(j=i-1; j>=0 && a[j]>temp; j--)    //從後向前查找待插入位置
                a[j+1] = a[j];                    //挪位
            a[j+1] = temp;                       //複制到插入位置
        }
}

//直接插入法二：用資料交換代替法一的資料後移(比較對象隻考慮兩個元素)
void InsertSort2(int a[], int n)
{
    for(int i=1; i<n; i++)
        for(int j=i-1; j>=0 && a[j]>a[j+1]; j--)
            Swap(a[j], a[j+1]);
}
void Swap(int a,int b){
    int temp;
    temp=a;
    a=b;
    b=temp;
}

最佳情況：T(n) = O(n) 最壞情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

4.希爾排序（Shell Sort）

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。希爾排序是把記錄按下表的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

基本步驟：在此我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2…1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，具體算法描述：

  • 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列個數k，對序列進行k 趟排序；
  • 每趟排序，根據對應的增量ti，将待排序列分割成若幹長度為m 的子序列，分别對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
排序操作的學習排序操作的學習
排序操作的學習排序操作的學習
//希爾排序法一
void shellSort1(int a[],int n){
    int i,j,gap,temp;
    for(gap = n/2;gap>0;gap/=2){
        for(i=gap;i<n;i+=gap){
            temp = a[i];
            for(j = i-gap;j>=0&&a[j]>temp;j-=gap){
                a[j+gap] = a[j];
            }
            a[j+gap] = temp;
        }
    }
}
//希爾排序法二，和上面的直接插入排序類似，用資料交換代替法一的資料後移(比較對象隻考慮兩個元素)
void ShellSort2(int a[], int n)
{
    int i, j, gap;
    //分組
    for(gap=n/2; gap>0; gap/=2)
        //直接插入排序
        for(i=gap; i<n; i++)
            for(j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap)
                Swap(a[j], a[j+gap]);
}

最佳情況：T(n) = O(nlog2 n) 最壞情況：T(n) = O(nlog2 n) 平均情況：T(n) =O(nlog2n)

5.歸并排序（Merge Sort）

和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是O(n log n）的時間複雜度。代價是需要額外的記憶體空間。歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序是一種穩定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。

排序操作的學習排序操作的學習
排序操作的學習排序操作的學習
//歸并排序思想
ElemType *b = (ElemType *) malloc ((n+1)*sizeof(ElemType)); //帶排序表有n個記錄
void Merge(ElemType a[],int low,int mid,int high){
    //表a中兩段a[low,...,mid]和a[mid+1,...,high]各自有序，将其合并成一個有序表
    for(int k=low;k<=high;k++)
        b[k]=a[k];             //将a中元素複制到輔助數組b中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(b[i]<=b[j])         //比較b的左右兩段中的元素
            a[k]=b[i++];       //将較小值複制到a中
        else
            a[k]=b[j++];
    }
    while(i<=mid)            //若左半部分表未檢測完，複制
        a[k++]=b[i++];   
    while(j<=high)           //若右半部分表未檢測完，複制
        a[k++]=b[j++];
}
void MergeSort(ElemType a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;            //從中間劃分2個子序列
        MergeSort(a,low,mid);            //對左側子序列進行遞歸排序
        MergeSort(a,mid+1,high);         //對右側子序列進行遞歸排序
        Merge(a,low,mid,high);           //歸并
    }
}

-------------------------------------------------------------------------------------------

//遞歸排序的完整實作
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
//合并兩個有序序列（即歸并）
// A： 待合并的序列（含兩個子序列，排在一起）
// Temp： 輔助空間
// L: 左邊序列起點下标
// R: 右邊序列起點下标，
// RightEnd： 右邊序列終點下标
void Merge(int A[], int Temp[], int L, int R, int RightEnd){
    int LeftEnd = R-1;
    int p=L,i;
    int num=RightEnd-L+1;
 
    //先合并最短序列的長度的個數個元素
    while(L<=LeftEnd&&R<=RightEnd){
 
        if(A[L]<=A[R])
            Temp[p++]=A[L++];
        else
            Temp[p++]=A[R++];
    }
 
    //判斷如果是左側序列還有剩餘
    while(L<=LeftEnd)
        Temp[p++]=A[L++];
    //判斷如果是右側序列還有剩餘
    while(R<=RightEnd)
        Temp[p++]=A[R++];
    // 将輔助空間中的值拷貝到原清單中，完成排序
    for(i=0;i<num;i++,RightEnd--)
        A[RightEnd]=Temp[RightEnd];
}
 
 
//遞歸拆分，遞歸歸并
void m_sort(int* arr, int* temp, int L, int right_end){
    int center;
    if(L<right_end){
        center = (L+right_end)/2;
        m_sort(arr,temp,L,center);
        m_sort(arr,temp,center+1,right_end);
        Merge(arr,temp,L,center+1,right_end);
    }
}
 
//歸并排序
void merge_Sort(int* arr,int length){
    int *temp=(int* )malloc(length*sizeof(int));  //申請輔助空間
    if(temp==NULL){
        return;
    }
    m_sort(arr,temp,0,length-1);
    free(temp);
    temp=NULL;
}
 
 
//列印元素
void printArr(int *arr,int length){
    for(int i=0;i<length;i++){
        printf("%d\n",arr[i]);
    }
}
 
 
int main(){
    int arr[10]={3,5,2,10,8,9,6,4,7,1};
    int length = sizeof(arr)/sizeof(int);
    length = 10;   
    merge_Sort(arr,length);    
    printArr(arr,length);
    return 0;
}

最佳情況：T(n) = O(n) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

6.快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

排序操作的學習排序操作的學習
//快速排序
void QuickSort(int a[],int left,int right){
    if(left<right){
        int i=left,j=right；
        int base=a[left];             //基準
        while(i<j){
            while(i<j&&a[j]>=base)    //從右往左找小于base的元素
                j--;
            if(i<j)
                a[i++]=a[j];
            while(i<j&&a[i]<base)    //從左往右找大于base的值
                i++;
            if(i<j)
                a[j--]=a[i];
        }
        a[i]=base;                  //将基準base填入最後的坑中
        QuickSort(a,left,i-1);      //遞歸調用，分治
        QuickSort(a,i+1,right);
    }
}

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)

三、總結

穩定性

穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

不穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

選擇排序算法準則

1.待排序的記錄數目n的大小；

2.記錄本身資料量的大小，也就是記錄中除關鍵字外的其他資訊量的大小；

3.關鍵字的結構及其分布情況；

4.對排序穩定性的要求。

算法 c語言
上一篇: RecyclerView中萬能Adapter
下一篇: HTML和CSS網頁布局相關知識

繼續閱讀