數據結構（十二）——排序算法

數據結構（十二）——排序算法

一、排序簡介

1、排序的一般定義

排序是計算機中經常進行的操作，目的在于將一組無序的數據元素調整為有序的數據元素。
序列：1，20，45，5，2，12
排序后：1，2，5，12，20，45

2、排序的數學定義

3、排序的穩定性

如果序列中的兩個元素R[i]、R[j]，關鍵字分別為K[i]、K[j]，并且在排序之前R[i]排在R[j]前面，如果排序操作后，元素R[i]仍然排在R[j]前面，則排序方法是穩定的；否則排序是不穩定的。

4、排序實現的關鍵

比較：任意兩個數據元素通過比較操作確定先后次序。
交換：數據元素需要交換才能得到預期的結果。

5、排序算法的性能評價

A、時間性能
主要性能差異體現在比較和交換的數量
B、輔助存儲空間
為完成排序操作需要的額外的存儲空間
必要時可以空間換時間
C、算法的實現復雜性
過于復雜的排序算法影響可讀性和可維護性

6、排序類

 class Sort:public Object
  {
  private:
    Sort();
    Sort(const Sort& other);
    Sort& operator = (const Sort& other);
    template <typename T>
    static void Swap(T& a, T& b)
    {
      T temp;
      temp = a;
      a = b;
      b = temp;
    }
  }

二、選擇排序

1、選擇排序簡介

每次（第i次，i=1,2,3,...,n-2）從后面n-i個待排序的數據元素中選出關鍵字最小的元素，作為有序序列的第i個元素。
第i次選擇排序示例：

選擇排序實例：

2、選擇排序的實現

選擇排序的實現：

 /******************************************
     * 排序方式：選擇排序
     * array:序列
     * len：序列中元素個數
     * min2max：按從小到大進行排序
     * ***************************************/
    template <typename T>
    static void Select(T array[], int len, bool min2max = true)
    {
      for(int i = 0; i < len; i++)
      {
          int min = i;//從第i個元素開始
          //對待排序的元素進行比較
          for(int j = i + 1; j < len; j++)
          {
              //按排序的方式選擇比較方式
              if(min2max?(array[min] > array[j]):(array[min] < array[j]))
              {
                  min = j;
              }
          }
          if(min != i)
          {
             //元素交換
             Swap(array[i], array[min]);
          }
      }
    }

選擇排序的時間復雜度為O（n^2）。
選擇排序是不穩定的排序方法。

三、插入排序

1、插入排序簡介

當插入第i（i>=1）個元素時，前i-1個元素已經排序好，用第i個元素的關鍵字與前i-1個元素的關鍵字分別進行比較，找到位置后將第i個元素插入，原來位置上的元素向后順移。
第i次插入排序示例：

插入排序實例：

2、插入排序的實現

/******************************************
 * 排序方式：插入排序
 * array:序列
 * len：序列中元素個數
 * min2max：按從小到大進行排序
 * ***************************************/
template <typename T>
static void Insert(T array[], int len, bool min2max = true)
{
    for(int i = 1; i < len; i++)
    {
            int k = i;
            T temp = array[i];
            for(int j = i -1; (j > 0) && (min2max?(array[j] > temp):(array[j] < temp)); j--)
            {
                    array[j + 1] = array[j];
                    k = j;
            }
            if(k != i)
            {
                    array[k] = temp;
            }
    }
}

插入排序的時間復雜度為O（n^2）
插入排序是穩定的排序方法。

四、冒泡排序

1、冒泡排序簡介

每次從后向前進行（第i次），j=n-1,n-2,...,i，比較V[j-1]和V[j]的關鍵字，如果發生逆序，則交換V[j-1]和V[j]。
第i次冒泡排序示例：

冒泡排序實例：

2、冒泡排序的實現

/**********************************************
 * 排序方式：冒泡排序
 * array:序列
 * len：序列中元素個數
 * min2max：按從小到大進行排序
 * *******************************************/
template <typename T>
static void Bubble(T array[], int len, bool min2max = true)
{
        bool exchange = true;
        //遍歷所有元素
        for(int i = 0; (i < len) && exchange; i++)
        {
                exchange = false;
                //將尾部元素與前面的每個元素作比較交換
                for(int j = len - 1; j > i; j--)
                {
                        if(min2max?(array[j] < array[j-1]):(array[j] > array[j-1]))
                        {
                                //交換元素位置
                                Swap(array[j], array[j-1]);
                                exchange = true;
                        }
                }
        }
}

冒泡排序的時間復雜度為O（n^2）
冒泡排序是穩定的排序方法。

五、希爾排序

1、希爾排序簡介

將待排序序列劃分為若干組，在每一組內進行插入排序，以使整個序列基本有序，然后再對整個序列進行插入排序。
將n個數據元素分成d個子序列，劃分方法如下:

d為增量，d的值在排序過程中由大到小逐漸縮小，直至最后一趟排序減為1。

2、希爾排序的實現

/******************************************
 * 排序方式：希爾排序
 * array:序列
 * len：序列中元素個數
 * min2max：按從小到大進行排序
 * ***************************************/
template <typename T>
static void Shell(T array[], int len, bool min2max = true)
{
        int d = len;
        do
        {
             d = d/3 + 1;
             for(int i = d; i < len; i += d)
             {
                     int k = i;
                     T temp = array[i];
                     for(int j = i -d; (j >= 0) && (min2max?(array[j] > temp):(array[j] < temp)); j -= d)
                     {
                             array[j+d] = array[j];
                             k = j;
                     }
                     if(k != i)
                     {
                                array[k] = temp;
                     }
             }
        }while(d > 1);
}
};

希爾排序通過分組的方法進行多次插入排序，是一種不穩定的排序方法，時間復雜度為O（n^(3/2)）。

六、歸并排序

1、歸并排序簡介

將兩個或兩個以上的有序序列合并成一個新的有序序列。

將2個有序序列歸并為一個新的有序序列，稱為2路歸并。
將N個有序序列歸并為一個新的有序序列，稱為N路歸并。
2路歸并實例：

2、歸并排序實現

template <typename T>
static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max=true)
{
        int i = begin;
        int j = mid + 1;
        int k = begin;
        while((i <= mid) && (j <= end))
        {
                if(min2max ? (src[i] < src[j]) : (src[i] > src[j]))
                {
                        helper[k++] = src[i++];
                }
                else
                {
                        helper[k++] = src[j++];
                }
        }
        while(i <= mid)
        {
                 helper[k++] = src[i++];
        }
        while(j <= end)
        {
                 helper[k++] = src[j++];
        }
        //拷貝輔助空間的結果到源序列空間
        for(i = begin; i <= end; i++)
        {
                src[i] = helper[i];
        }
}
template <typename T>
static void Merge(T src[], T helper[], int begin, int end, bool min2max=true)
{
        if(begin < end)
        {
                int mid = (begin + end) / 2;
                //左邊路進行歸并排序
                Merge(src, helper, begin, mid, min2max);
                //右邊路進行歸并排序
                Merge(src, helper, mid+1, end, min2max);
                //二路歸并排序
                Merge(src, helper, begin, mid, end, min2max);
        }
}
/******************************************
* 排序方式：歸并排序
* array: 序列
* len：序列中元素個數
* min2max：按從小到大進行排序
* ***************************************/
template <typename T>
static void Merge(T* array, int len, bool min2max=true)
{
    //輔助空間申請
    T* helper = new T[len];
    if(helper != NULL)
    {
        Merge(array, helper, 0, len-1, min2max);
    }
    delete [] helper;
}

歸并排序是一種穩定排序，需要額外的輔助空間完成，空間復雜度為O（n），時間復雜度為O(nlogn)。

七、快速排序

1、快速排序簡介

任取序列中的某個數據元素作為基準將整個序列劃分為左右兩個子序列。左側子序列中所有的數據元素都小于或等于基準元素，右側子序列中所有元素都大于基準元素，基準元素排在兩個子序列中間。
分別對兩個子序列進行重新劃分，直到所有的數據元素都排在相應位置上為止。
快速排序示例：

快速排序實例：

2、快速排序實現

/******************************************
 * 快速排序的區域劃分函數
 * array:序列
 * begin：序列的起始位置
 * end：序列的結束位置
 * min2max：按從小到大進行排序
 * ***************************************/
template <typename T>
static int Partition(T array[], int begin, int end, bool min2max)
{
        T pv = array[begin];
        while(begin < end)
        {
                while((begin < end) && (min2max ? (array[end] > pv): (array[end] < pv)))
                {
                        end--;
                }
                Swap(array[begin], array[end]);
                while((begin < end) && (min2max ? (array[end] <= pv): (array[end] > pv)))
                {
                        begin++;
                }
                Swap(array[begin], array[end]);
        }
        array[begin] = pv;
        return begin;
}

/******************************************
 * 快速排序功能函數
 * array: 序列
 * begin：序列的起始位置
 * end: 序列的結束位置
 * min2max：按從小到大進行排序
 * ***************************************/
template <typename T>
static void Quick(T array[], int begin, int end, bool min2max)
{
        if(begin < end)
        {
            //對序列進行區域劃分
            int pivot = Partition(array, begin, end, min2max);
            //對基準左側的區域進行快排序
            Quick(array, begin, pivot, min2max);
            //對基準右側的區域進行塊排序
            Quick(array, pivot+1, end, min2max);
        }
}
/******************************************
* 排序方式：快速排序
* array: 序列
* len：序列中元素個數
* min2max：按從小到大進行排序
* ***************************************/
template <typename T>
static void Quick(T array[], int len, bool min2max=true)
{
    Quick(array, 0, len-1, min2max);
}

快速排序通過遞歸的方式對排序問題重新劃分，是一種不穩定的排序方法，時間復雜度為O（nlogn）。

八、排序的工程應用

1、排序算法面向數組類的實現

 template <typename T>
  static void Select(Array<T>& array, bool min2max=true)
  {
      Select(array.array(), array.length(), min2max);
  }

  template <typename T>
  static void Insert(Array<T>& array, bool min2max=true)
  {
      Insert(array.array(), array.length(), min2max);
  }

  template <typename T>
  static void Bubble(Array<T>& array, bool min2max=true)
  {
      Bubble(array.array(), array.length(), min2max);
  }

  template <typename T>
  static void Shell(Array<T>& array, bool min2max=true)
  {
      Shell(array.array(), array.length(), min2max);
  }

  template <typename T>
  static void Merge(Array<T>& array, bool min2max=true)
  {
      Merge(array.array(), array.length(), min2max);
  }

  template <typename T>
  static void Quick(Array<T>& array, bool min2max=true)
  {
      Quick(array.array(), array.length(), min2max);
  }

2、大規模序列的排序問題

排序過程中不可避免的需要進行交換操作，交換操作的本質為數據元素間的相互復制，如果序列的規模巨大時，交換操作將耗時巨大。
通過使用代理模式，為待排序元素設置代理對象，對代理對象組成的序列進行排序，需要訪問有序序列元素時，通過訪問待序列完成。
通過使用空間換時間提高算法效率。