Sort Algorithms

本文是各种排序算法的汇总。

1. Insertion Sort

基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。想想插入扑克牌的例子。

void InsertionSort(vector<int> &nums) {
    if (nums.empty() == NULL) return;
    for (int j = 1; j < nums.size(); j++) {
        int key = nums[j]; //for a given record j
        int i = j - 1; //fint the right postion from 0~j-1
        while (i >= 0 && nums[i] > key) {
            nums[i + 1] = nums[i];
            i--;
        } //after this inner loop, i is -1 or nums[i]<=key, so i+1 is the right place for key
        nums[i + 1] = key; //inset key at the right place
    }
}
  • O(n^2) run time, O(1) space
  • 稳定，适用于少量元素的排序

2. Merge Sort

基本思想：分治。

  1. 分解：将当前区间一分为二，即求分裂点
  2. 求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
  3. 组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
void Merge(vector<int> &nums, int low, int mid, int high) {
    //merge nums[low...mid] and nums[mid+1, high]
    //vector<int> cpy(nums.begin() + low, nums.begin() + high + 1);//backup of nums
    /*vector<int> cpy = nums;
    int i = low;//start of the first sorted part
    int j = mid + 1; //second
    for (int k = low; k <= high; k++) {
        if (i > mid) nums[k] = cpy[j++];
        else if (j > high) nums[k] = cpy[i++];
        else if (cpy[i] < cpy[j]) nums[k] = cpy[i++];
        else nums[k] = cpy[j++];
    }*/

    vector<int> part1(nums.begin() + low, nums.begin() + mid + 1);
    vector<int> part2(nums.begin() + mid + 1, nums.begin() + high + 1);
    int i = 0, j = 0;
    int len1 = part1.size();
    int len2 = part2.size();
    for (int k = low; k <= high; k++) {
        if (i > len1-1) nums[k] = part2[j++];
        else if (j > len2-1) nums[k] = part1[i++];
        else if (part1[i] < part2[j]) nums[k] = part1[i++];
        else nums[k] = part2[j++];
    }
}
void MergeSort(vector<int> &nums, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    MergeSort(nums, low, mid);
    MergeSort(nums, mid + 1, high);
    Merge(nums, low, mid, high);
}

虽然插入排序的时间复杂度为O(n^2)，归并排序的时间复杂度为O(nlogn)，但插入排序中的常数因子使得它在n较小时，运行得要更快一些。因此，在归并排序算法中，当子问题足够小时，采用插入排序算法就比较合适了。另外归并排序需要O(n)space也是它的弱点。

另外在merge函数中每次都要构造子数组，注释掉的部分更差劲，每次都要copy整个数组！！这样的话创建新数组将消耗掉大量的时间。一个解决办法是构造一个类，将cpy数组作为成员变量，每次Merge函数里只要copy从low到high的部分作为备份即可。但是这样做也是不妥的，因为有可能有多个程序同时使用这个类，更好的方法是可以将cpy数组作为参数传递给MergeSort的方法。

3. Quick Sort

基本思想：先切分，再排序，分治的思想。跟并归排序是互补的思想。

 int partition(vector<int> &nums, int start, int end) {
     int pivot = nums[end];
     int i = start - 1;
     for (int j = start; j < end; j++) {
         if (nums[j] <= pivot) {
             i++;
             swap(nums[i], nums[j]);
         }
     }
     swap(nums[end], nums[++i]);
     return i;
 }
 //sort nums betwenn start and end, [start, end]
 void QuickSort(vector<int> &nums, int start, int end) {
     if (start >= end) return;
     int mid = partition(nums, start, end);
     QuickSort(nums, start, mid - 1);
     QuickSort(nums, mid + 1, end);
 }

算法的改进：

  1. 在排序小数组时切换到插入排序。将if (start >= end) return换成if (end <= start + M) call InsertationSort(nums, start, end)
  2. 如果pivot选最后一个元素总是最大数，算法复杂度变为O(n^2). 解决办法是不要总选最右一个元素作为pivot，随机化选取。
  3. 除了随机化选取，还可以根据三取样切分来确定pivot。根据是：当我们采取data[lo],data[mid],data[hi]三者之中的那个第二大的元素为主元时，便能尽最大限度保证快速排序算法不会出现O（N^2）的最坏情况。因此还是在partition函数中，选取nums[start], nums[end], nums[mid]三者中第二大的元素作为pivot。
  4. 如果数组里有很多重复元素，算法复杂度变为平方级别，解决办法是三向切分的快速排序。将数组切分成三部分，分别对应于小于，等于和大于切分元素的数组元素。

算法的优缺点：

  1. 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
  2. 平均时间复杂度为O(nlgn)

4. Selection Sort

基本思想非常的直观：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 以此类推，直到所有元素均排序完毕。
 void SelectionSort(vector<int> &nums) {
     for (int i = 0; i < nums.size(); i++) {
        // Exchange a[i] with smallest entry in a[i+1...N).
         int idx = i;//index of minimal entr.
         for (int j = i + 1; j < nums.size(); j++) {
             if (nums[j] < nums[idx]) {
                 //key = nums[j];
                 idx = j;
             }
         }
         swap(nums[i], nums[idx]);
     }     
 }

选择排序的特点：

  1. 最好最坏的情况都是O(n^2)复杂度，O(1) space
  2. 移动数据是最小的，选择排序用了N次交换，和数组大小成线性关系，其他任何排序算法都不具备这个特征。
  3. 不稳定

5. Heap Sort

关于堆的几个概念:

  • 堆数据结构在物理上是一种数组对象，逻辑上它可以被视为一棵近似完全二叉树。树中每个节点与数组中存放该节点值的那个元素对应。 树的每一层都是填满的，最后一层除外。换句话说：堆用数组表示，用完全二叉树理解。

  • 堆满足二个特性：

    1. 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
    2. 每个结点的左子树和右子树都是一个二叉堆（最大堆或最小堆）。

  • 当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。
    当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

  • 在索引从0开始的数组a[N]中：

    • 父节点 i 的左子节点在位置(2*i+1)
    • 父节点 i 的右子节点在位置(2*i+2)
    • 子节点 i 的父节点在位置floor((i-1)/2)
    • a[0~N/2-1]是非叶子，a[N/2, N-1]是叶子
      给定个数组范围a[low, high], a[low, (high-low-1)/2]是非叶子

关于堆的几个操作（以最大堆为例）：

  1. 最大堆调整（Max_Heapify）：调整以某个元素i为根节点的子树，使得子节点永远小于父节点，并且调整以后两个子节点为根节点的子树也要满足最大堆。所以有个递归的调整，一直调整到数组最右端。时间复杂度取决于该元素i所在高度。如果是堆顶元素那平均时间复杂度是O(logN).
  2. Insert（插入），将X插入一个堆中，在数组尾部增加一个元素X，然后向上冒泡，知道X放入合适位置，也就是两个子节点都小于X。平均时间复杂度O(1)最坏O(logN)。对应于priority_queue中的push。实现的时候就是：把X放入队尾，然后跟他的父节点i/2去比，看要不要往上冒，一直往上到不能再冒。
  3. 创建最大堆（Build_Max_Heap）：从倒数第一个非叶子节点N/2-1开始自底向上依次调用MaxHeapfiy函数。或者调用Insert函数N次。所以时间复杂度平均为O(N),O(NlogN)最坏时间。
  4. DelteMax(删除堆顶元素）。对应于priority_queue中的pop。将堆顶元素(a[0])和最后一个元素(a[N-1])交换，然后调用调整函数Max_Heapify(a, 0, N-1)。时间复杂度是O(logN)
  5. 堆排序（HeapSort）：调用N次DelteMax，所以时间复杂度是O(NlogN)。
 void MaxHeap(vector<int> &a, int i, int right) {
     int max_index = i;
     int l_index = i * 2 + 1;//left node
     int r_index = i * 2 + 2;//right node
     //find which one is the largest
     if (l_index <= right && a[l_index] > a[max_index]) {
         max_index = l_index;
     }
     if (r_index <= right && a[r_index] > a[max_index]) {
         max_index = r_index;
     }
     //if max_index is NOT i, swap it
     //如果a[i]是最大的，则以i为根的子树已是最大堆, 否则i的子节点有最大元素  
     //则交换a[i],a[max_index],从而使i及子女满足堆性质 
     if (max_index != i) {
         swap(a[i], a[max_index]);
         //adjust heap 重新调整以max_index为根的子树
         MaxHeap(a, max_index, right);
     }

 }

 //convert a to a max_heap
 void BuildMaxHeap(vector<int> &a) {
     int n = a.size();
     for (int i = (n - 1) / 2; i >= 0; i--) {//叶子节点已经是堆了，调整所有非叶子节点，自底向上
         MaxHeap(a, i, n-1);
     }
 }

 void HeapSort(vector<int> &a) {
     BuildMaxHeap(a);
     for (int right = a.size() - 1; right > 0;) {
         swap(a[0], a[right--]);
         MaxHeap(a, 0, right);
     }
 }

 void Insert(vector<int> &heap, int val) {
        heap.emplace_back(val);
        int i = heap.size()-1; //the postion of the new value
        //bottom-up heapify it
        while(i>0 && heap[i] < heap[(i-1)/2]) {
           swap(heap[i], heap[(i-1)/2]);
           i = (i-1)/2;
        }
    }

关于优先队列priority_queue的使用 参考

  1. priority_queue就是C++里的堆的具体实现，它的接口和复杂度参照上面的描述。
  2. 他的模板声明带有三个参数，priority_queue < Type, Container, Functional> Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator <, 所以如果你把后面俩个 参数缺省的话，优先队列就是大顶堆，队头元素最大。为什么最大堆用的是小于号呢？因为在调整函数MaxHeap中只有当前结点比它的子节点小的时候才需要调整。
  3. 最大堆声明：priority_queue <int> q
    最小堆声明priority_queue<int, vector<int>, greater<int> > q;

  4. 如果是自定义的数据类型呢？需要重载operator < 

    class Node {
 public:
     int a;
     string b;
     Node(int _a, string _b) {
         a = _a;
         b = _b;
     }
     bool operator< (const Node& B) const {
         if(a==B.a) return b > B.b;
         return a < B.a;
     }

 };
 //声明一个最大堆：
 priority_queue<Node> que;

    做题：http://www.lintcode.com/en/problem/top-k-frequent-words/
    参考： 最小的K个数（Top K问题） 《数据结构与算法分析C语言实现》6.4

results matching ""

    No results matching ""