排序算法综述

排序算法有很多种,本文主要介绍基本的排序算法和实现,并分析复杂度和稳定性。

 

一、Ο(n2)的算法

  1、插入排序

  插入排序十分好理解,在无序的数组中选择一个数值,插入到有序的数组当中,这个过程是稳定的。实现代码如下:

  

技术分享
1 template <typename T>
2 void InsertionSort(vector<T> &arr){
3     int i, j;
4     for (i = 1; i < arr.size(); i++) {
5         int temp = arr[i];
6         for (j = i - 1; j >= 0 && arr[j] > temp; j--)
7             arr[j + 1] = arr[j];
8         arr[j + 1] = temp;
9     }
InsertionSort

  2、冒泡排序

  冒泡排序的过程是遍历数组,每次选取一个数值往前比较,大于前一个数值就交换,直到遇到更大的数值或遍历完数组,这个过程本身也是稳定的。

技术分享
template <typename T>
void BubbleSort(vector<T> &arr){
    for (int i = 0; i != arr.size(); i++){
        for (size_t j = 0; j < arr.size()-1-i ; j++)
        {
            if (arr[j] > arr[j + 1]){
                arr[j] = arr[j] ^ arr[j+1];
                arr[j+1] = arr[j] ^ arr[j+1];
                arr[j] = arr[j+1] ^ arr[j];
            }
        }
    }
}
BubbleSort


 

二、Ο(nlogn)的算法

 

  1、归并排序

    归并排序是典型的分治算法,把原问题划分为不相交的子问题。代码如下:

    

技术分享
 1 void Merge(vector<int> &arr,int l,int m,int r){
 2     vector<int> Left, Right;
 3     int n1 = m - l; int n2 = r - m;
 4     for (int i = 0; i <= n1 ; i++)
 5         Left.push_back(arr[l + i]);
 6     Left.push_back(infinite);//哨兵值
 7     for (int i = 0; i != n2; i++)
 8         Right.push_back(arr[m + i + 1]);
 9     Right.push_back(infinite);
10     int index1 = 0;int index2 = 0;
11     for (int i = l; i != r + 1; i++){
12         if (Left[index1] < Right[index2])
13             arr[i] = Left[index1++];
14         else
15             arr[i] = Right[index2++];
16     }
17 };
18 
19 
20 void MergeSort(vector<int> &arr, int l, int r){
21     
22     if (l < r){
23         int m = int((l + r) / 2);
24         MergeSort(arr, l, m);
25         MergeSort(arr, m + 1, r);
26         Merge(arr, l, m, r);
27     }
28 }
MergeSort

 

  2、堆排序

    堆排的本质就是维护一个最大堆(最小堆),所以他的时间复杂度是与最大堆的性质相联系的,一个最大堆的Deletemax操作是O(1)的,而每次DeleteMax后要维护最大                堆的性质,所以维护堆的时间复杂度是O(logn)的,合起来就是O(nlogn)。代码实现与建堆类似,就不赘述。

    

  3、快速排序

    快排也是分治的思想,选取一个主元,将数组分为两个部分,一个部分小于它另一个部分大于它,然后递归两个子数组直到排序完成。快排和主元的选取有关,如果选取的        结果恰好是排好序的,那么时间复杂度将会变成O(n2)。

    代码如下:

    

 1 int Partition(vector<int> &arr, int left, int right){
 2     int i = left - 1;
 3     for (int j = left; j < right; j++){
 4         if (arr[j] <= arr[right])
 5             std::swap(arr[++i], arr[j]);
 6     }
 7     std::swap(arr[i + 1], arr[right]);
 8     return i + 1;
 9 }
10 void QuickSort(vector<int> &arr,int left,int right){
11     if (left < right){
12         int mid = Partition(arr, left, right);
13         QuickSort(arr, left, mid-1);
14         QuickSort(arr, mid+1, right);
15     }
16 
17 }

 

三、线性算法(以后介绍)

  

  1、基数排序

  2、计数排序

  3、桶排序

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。