8大排序算法的总结

• 常见算法思想;
• 简介
  • 插入排序
  • 冒泡排序
  • 直接插入排序
  • 折半插入排序
  • 归并排序
  • 快速排序
  • 希尔排序
  • 堆排序
  • 直接选择排序
• 稳定性比较
  • 快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法;
  • 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法;
  • 稳定排序的意思是: 假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的;
    • 简单理解就是保持了相同元素在原来序列中的先后关系;
• 快速排序的代码:

#include "../leetcodeutil.h"

int patition(vector<int>& nums, int l, int r) {
    int pivot = nums[r];        // 以最右边为轴
    int i = l;
    for(int j = i; j < r; ++j) {
        if(nums[j] < pivot) {
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[r]);

    return i;   // 返回最后的轴点
}
// int patition(vector<int>& nums, int l, int r) {
//     int pivot = nums[l];   // 以最左边为轴
//     int i = r;
//     for(int j = i; j >= l; --j) {
//         if(nums[j] > pivot) {
//             swap(nums[i--], nums[j]);
//         }
//     }
//     swap(nums[i], nums[l]);

//     return i;   // 返回最后的轴点
// }

void quicksortutil(vector<int> &nums, int l, int r) {
    if(l < r) {
        int pivot = patition(nums, l, r);
        quicksortutil(nums, l, pivot - 1);
        quicksortutil(nums, pivot + 1, r);
    }
}

void quicksort(vector<int> &nums) {
    quicksortutil(nums, 0, nums.size() - 1);
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    quicksort(iv);
    cout << iv << endl;

    return 0;
}

• 冒泡排序源码

#include "../leetcodeutil.h"

void bubblesort(vector<int> &nums) {
    int len = nums.size();
    if(len == 0) return;
    for(int i = 0; i < len; ++i) {
        for(int j = len - 1; j > i; --j) { // 正宗的冒泡排序应该是从后往前排
            if(nums[j] < nums[j-1]) {      // 从后往前找, 找出小的交换
                swap(nums[j], nums[j-1]);
            }
        }
    }
}
// 优化的冒泡排序, 可以去掉本身有序的情况
void bubblesort2(vector<int> &nums) {
    int len = nums.size();
    if(len == 0) return;            // 时间复杂度还是O(n2)的
    bool isUnordered = true;        // 减枝优化, 如果本身就是有序, 直接返回
    for(int i = 0; i < len && isUnordered; ++i) {
        isUnordered = false;
        for(int j = len - 1; j > i; --j) {
            if(nums[j] < nums[j-1]) {      //从后往前找, 找出小的交换
                swap(nums[j], nums[j-1]);
                isUnordered = true; // 进行了一次交换, 证明之前是无序的;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    // bubblesort(iv);
    bubblesort2(iv);
    cout << iv << endl;

    return 0;
}

• 希尔排序源码

#include "../leetcodeutil.h"

void shellsort(vector<int> &nums) {
    // 希尔排序就是有增量的直接插入排序，所以将原先直接插入代码修改一下，把步进长度改为增量即可
    int len = nums.size();
    int i, j;
    int increment = len;
    int key;
    while(increment > 1) {
        increment = increment/3 + 1;     // 增量序列
        for(i = increment; i < len; i++) {
            key = nums[i];
            j = i - increment;
            while(j >= 0) {
                if(key < nums[j]) {
                    int tmp = nums[j];
                    nums[j] = key;
                    nums[j+increment] = tmp;
                }
            }
            j = j - increment;
        }
    }
}


int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    shellsort(iv);
    cout << iv << endl;

    return 0;
}

• 选择排序的源码

#include "../leetcodeutil.h"
// 大概的思路就是找到最小的元素, 并与之交换
void selectionsort(vector<int> &nums) {
    int len = nums.size();
    if(len == 0) return;
    for(int i = 0; i < len; ++i) {
        int min = i;
        for(int j = i+1; j < len; j++) {
            if(nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums[i], nums[min]);
    }
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    selectionsort(iv);
    cout << iv << endl;

    return 0;
}

• 插入排序的源码

#include "../leetcodeutil.h"
// 插入排序的的思想是找到相应的位置插入进去
void insertionsort(vector<int> &nums) {
    int len = nums.size();
    if(len == 0) return;
    for(int i = 1; i < len; ++i) {
        int val = nums[i];
        int j = i - 1;
        while(j >= 0 && nums[j] > val) {
            nums[j+1] = nums[j];
            --j;
        }
        nums[j+1] = val;
    }
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    insertionsort(iv);
    cout << iv << endl;

    return 0;
}

• 归并排序的源码

#include "../leetcodeutil.h"

using namespace std;

void merge(vector<int>& nums, int l, int m, int r) {
    int n1 = m - l + 1; // 第一部分数组的长度
    int n2 = r - m;     // 第二部分数组的长度
    int L[n1], R[n2];   // 将数组元素复制到临时数组
    for(int i = 0; i < n1; ++i) {
        L[i] = nums[l+i];
    }
    for(int i = 0; i < n2; ++i) {
        R[i] = nums[m+i+1];
    }
    // vector<int> L(nums.begin() + l, nums.begin() + m + l);
    // vector<int> R(nums.begin()+m+l, nums.begin()+r+1);
    // 将两个临时数组归并到nums[l,···,r]
    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2) {
         nums[k++] = L[i] < R[j] ? L[i++] :   // 那个小就放前面
                                   R[j++];
    }
    // 如果有一个数组有剩余的部分就完全复制拷贝就OK
    // 拷贝L[]剩下的元素
    while(i < n1) {
        nums[k++] = L[i++];
    }
    // 拷贝R[]剩下的元素
    while(j < n2) {
        nums[k++] = R[j++];
    }
}

void mergesortutil(vector<int>& nums, int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;    //防止溢出
        mergesortutil(nums, l, m);
        mergesortutil(nums, m+1, r);
        merge(nums, l, m, r);
    }
}

void mergesort(vector<int> &nums) {
    if(nums.size() == 0) 
        return;
    mergesortutil(nums, 0, nums.size()-1);
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    mergesort(iv);
    cout << iv << endl;

    return 0;
}

• 堆排序的源码

#include "../leetcodeutil.h"

using namespace std;
// 堆排序的关键是在于建堆(堆本质上可以看做是一个二叉树, 根节点为最大或最小值)
// 调整以root为根节点的子树, 使其符合最大堆, 其中n为堆结构的节点数
void heapAdjust(vector<int> &nums, int n, int root) {
    int max_ = root;
    int L = 2*root + 1;     // 左孩子
    int R = 2*root + 2;     // 右孩子
    // 左孩子大于根
    if(L < n && nums[L] > nums[max_]) {
        max_ = L;
    }
    if(R < n && nums[R] > nums[max_]) {
        max_ = R;
    }
    // 最大的元素不是根
    if(max_ != root) {
        swap(nums[root], nums[max_]);
        heapAdjust(nums, n, max_);  // 递归调整以max_为根的子树
    }
}

void heapsort(vector<int> &nums) {
    int len = nums.size();
    // 创建最大堆, 重新排列数组
    for(int i = len/2 - 1; i >= 0; --i) {
        heapAdjust(nums, len, i);
    }
    // 堆排序将依次把根元素移动到数组尾部, 并进行调整
    for(int i = len-1; i >= 0; --i) {
        swap(nums[0], nums[i]); // 第一个元素始终是根元素, 把根元素放到数组的末尾
        heapAdjust(nums, i, 0); // 注意堆中的元素是逐个减少的
    }
}

int main(int argc, char const *argv[])
{
    vector<int> iv{1,31,12,23,5,11,7,2,4,6,8,0,21,34,1321,3};
    heapsort(iv);
    cout << iv << endl;

    return 0;
}

• leetcodeutil.h头文件是刷题自己写的接口

#ifndef _LEET_CODE_UTIL_H_
#define _LEET_CODE_UTIL_H_
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 二叉树结点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 打印vector中的所有元素
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v)
{
    for (int i = 0; i < v.size(); ++i) {
        i == 0 ? out << v[i] : cout << ' ' << v[i];
    }
    return out;
}
// 打印二维vector中的所有元素
template <typename T>
ostream& operator<<(ostream& out, const vector<vector<T>>& v) {
    for (int i = 0; i < v.size(); ++i) {
        i == 0 ? out << v[i] : out << '\n' << v[i];
    }
    return out;
}
// 以initializer_list来初始化链表
template <typename T>
ListNode* createList(const initializer_list<T>& v) {
    ListNode dummy(0);
    ListNode* prev = &dummy;
    for (const auto& e : v) {
        prev->next = new ListNode(e);
        prev = prev->next;
    }
    return dummy.next;
}
// 销毁链表
void destroyList(ListNode* &head) {
    ListNode* curr = head, *next;
    while (curr) {
        next = curr->next;
        delete curr;
        curr = next;
    }
    head = NULL;
}
// 打印链表元素
ostream& operator<<(ostream& out, const ListNode* list) {
    while (list != NULL) {
        list->next == NULL ? out << list->val : out << list->val << ' ';
        list = list->next;
    }
    return out;
}
// 前序遍历二叉树
void preorderTraverseTree(TreeNode *root) {
    if (root == NULL) return;
    cout << root->val << ' ';
    preorderTraverseTree(root->left);
    preorderTraverseTree(root->right);
}
// 中序遍历二叉树
void inorderTraverseTree(TreeNode *root) {
    if (root == NULL) return;
    inorderTraverseTree(root->left);
    cout << root->val << ' ';
    inorderTraverseTree(root->right);
}
// 后序遍历二叉树
void postorderTraverseTree(TreeNode *root) {
    if (root == NULL) return;
    postorderTraverseTree(root->left);
    postorderTraverseTree(root->right);
    cout << root->val << ' ';
}
// 层序遍历二叉树
void levelorderTraverseTree(TreeNode *root) {
    if (root == NULL) return;
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    while (!q.empty()) {
        curr = q.front();
        cout << curr->val << ' ';
        if (curr->left)  q.push(curr->left);
        if (curr->right) q.push(curr->right);
        q.pop();
    }
}
// 根据层序遍历的 vector 构造二叉树递归函数
static TreeNode* createTree(const vector<int>& nums, int n) {
    if (nums[n] == '#') return NULL;
    TreeNode *node = new TreeNode(nums[n]);
    int len = nums.size();
    int left  = n*2 + 1;
    int right = n*2 + 2;
    node->left  = left  < len ? createTree(nums, left)  : NULL;
    node->right = right < len ? createTree(nums, right) : NULL;
    return node;
}
// 根据层序遍历的 initializer_list 构造二叉树
template <typename T>
TreeNode* createTree(const initializer_list<T>& nums) {
    vector<T> v;
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        v.push_back(*it);
    }
    return createTree(v, 0);
}
// 随机数辅助类
class MathUtil {
public:
    // 产生[a, b)之间的随机数
    static int random(int a, int b) {
        assert(b > a);
        return a + rand() % (b-a);
    }
};
struct SrandInitalizer {
    SrandInitalizer() { srand(time(NULL)); }
};
SrandInitalizer _srandinit;
// 时间辅助类
class TimeUtil {
public:
  // 返回当前进程运行的时间 (单位: ms)
  static int getCurrentTimeMs() { return (int)clock() / (CLOCKS_PER_SEC / 1000); }
  // 返回当前进程运行的时间 (单位: us)
  static int getCurrentTimeUs() { return (int)clock() / (CLOCKS_PER_SEC / 1000000); }
};

#endif // _LEET_CODE_UTIL_H_