计算机经典排序算法——C++实现

作者: 田田ww | 来源:发表于2019-04-09 21:54 被阅读0次

计算机笔试经典排序方法总结如下：

计算机经典排序算法

按照上图我们依次介绍不同排序算法及其具体代码实现(升序)。

1.直接插入排序

实现原理：将一个数据插入到已排好序的有序数据中，从而得到一个新的，个数加一的有序数据，在数据量较小时比冒泡排序和简单选择排序性能好一些。

插入排序

时间复杂度： $O(n^2)$

空间复杂度： $O(1)$

稳定性：稳定（相同大小的数据，在原无序记录和排好序的记录中前后顺序不被交换）

c++代码：

vector<int> InsertSort::sort(vector<int> ivec) {
    int j = 0;
    for (int i = 1; i < ivec.size(); i++) {
        if (ivec[i] < ivec[i - 1]) {
            j = i;
            while (j > 0 && ivec[j] < ivec[j - 1]) {
                swap(ivec[j], ivec[j - 1]);
                j --;
            }
        }
    }
    return ivec;
}

2.冒泡排序

实现原理：比较相邻两数的大小关系，在一趟冒泡排序过程中可以从原数据中选取最大或最小值，在循环过程中从剩余数据中依次选取最值。

冒泡排序

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定

算法

比较相邻的元素，如果前大于后，交换；

对每一对相邻元素进行该操作，直到结尾则此时最后元素最大；

重复以上步骤，每次除去上一轮最后一个元素；

重复步骤1-3直到排序完成。

C++代码：

vector<int> BubboSort::sort(vector<int> ivec) {
     for (int i = 0; i < ivec.size(); i ++) {
         for (int j = 1; j < ivec.size() - i; j++) {
             if (ivec[j - 1] > ivec[j]){
                 swap(ivec[j], ivec[j - 1]);
             }
         }
     }
     return ivec;
 }

3.快速排序

实现原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序

时间复杂度： $O(nlogn)$
空间复杂度： $O(logn)$

算法

从数据中挑出一个元素，称为“基准”（pivot）；

重新排序数列，所有元素比基准值小放在基准值前，大放在后，相同均可。则这次分区后该基准处于数列中间位置，称为“分区”（partition）操作；

递归地(recursive)把小于基准值的元素的数列和大于基准值的数列进行排序。

C++代码：

void quickSort(vector<int> &vec, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = vec[left], l = left, r = right;
    while (l < r) {
        while (l < r && vec[r] >= pivot) {
            r --;
        }
        while (l < r && vec[l] <= pivot) {
            l ++;
        }
        if (l < r) {
            swap(vec[l], vec[r]);
        }
    }
    swap(vec[left], vec[l]);
    quickSort(vec, left, l - 1);
    quickSort(vec, l + 1, right);
}

vector<int> QuickSort::sort(vector<int> ivec) {
    int left = 0;
    int right = ivec.size()-1;
    quickSort(ivec, left, right);
    return ivec;
}

4.选择排序

实现原理：首先在未排序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续找最小（大）元素，放到已排序列末尾。

选择排序

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$
稳定性：不稳定

算法

初始状态：无序区为R[1,2,...,n]，无序区为空；

第i趟排序（i=1,2,...,n-1）开始前，当前有序区和无序区分别为R[1,2,...,i-1]和R[i,i+1,...,n]。该趟从无序区中选出关键字最小的记录R(k)，将他与无序区第1个记录R(i)交换，使R[1,2,...,i]和R[i+1,...,n]分别变为个数增加1的新有序区和记录个数减少1的新无序区；

n-1趟结束，数列变为有序。

C++代码：

vector<int> InsertSort::sort(vector<int> ivec) {
    for (int i = 0; i < ivec.size(); i ++) {
        int minIndex = i;
        for (int j = i + 1; j < ivec.size(); j++) {
            if (ivec[j] < ivec[minIndex]) {
                minIndex = j;
            }
        }
        swap(ivec[i], ivec[minIndex]);
    }
    return ivec;
}

5.堆排序

实现原理：利用堆这种数据结构设计的一种算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或大于）其父结点。

堆排序

堆的定义：n个元素的序列 $\{ k_1,k_2,...,k_n\}$ 当且仅当满足以下条件时称为堆。
小顶堆 $\left\{\begin{aligned} k_i \leq k_{2i} \\ k_i \leq k_{2i+1}\end{aligned}\right.(i = 1,2,...)$
大顶堆 $\left\{\begin{aligned} k_i \geq k_{2i} \\ k_i \geq k_{2i+1}\end{aligned}\right.(i = 1,2,...)$
时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$
稳定性：不稳定

算法

将初始待排序关键字序列 $R[1,2,...,n]$ 构成大顶堆，此堆为初始无序区

将堆顶元素 $R[1]$ 与最后一个元素 $R[n]$ 交换，此时得到新的无序区 $R[1,2,...,n-1]$ 和新的有序区 $R[n]$ ，且满足 $R[1,2,...,n-1] \leq R[n]$ 。

交换后对当前无序区 $R[1,2,...,n-1]$ 调整为新堆，然后再次将 $R[1]$ 与无序区最后一个元素交换，得到新的无序区 $R[1,2,...,n-2]$ 和新的有序区 $R[n-1,n]$ ，不断重复此过程直到有序区元素个数为n-1，则整个排序过程完成

C++代码

//递归方法进行堆调整
void heapAjust(vector<int> &ivec, int p, int lenl) {
    //p待调整的节点下标
    //len待调整的数组长度
    int parent = p;
    int leftchild = 2 * parent + 1;
    int rightchild = 2 * parent + 2;
    if (leftchild < lenl && ivec[leftchild] > ivec[parent]) {
        parent = leftchild;
    }
    if (rightchild < lenl && ivec[rightchild] > ivec[parent]) {
        parent = rightchild;
    }
    if (parent != p) {
        swap(ivec[parent], ivec[p]);
        heapAjust(ivec, parent, lenl);
    }
}
//非递归方法进行堆调整
void heapAjust(vector<int> &ivec, int p, int len){
//每次判断根节点和左右孩子节点的大小关系，比最大的孩子节点小则交换
        for(int i = 2*p +1; i < len; i = 2*i + 1){
              if(i + 1 < len && ivec[i] < ivec[i + 1]) i++;
              if(ivec[i] > ivec[p]){
                  swap(ivec[i], ivec[p]);
                  p = i;
              }
              else break;
        }
}
vector<int> HeapSort::sort(vector<int> ivec){
    int len = ivec.size();
    //初始化堆
    for (int i = len / 2; i >= 0; i--) {
        heapAjust(ivec, i, len);
    }
    //排序
    for (int t = len - 1; t >= 0; t--) {
        swap(ivec[0], ivec[t]);
        heapAjust(ivec, 0, t);
    }
    return ivec;
}

6.归并排序

实现原理：归并排序（MERGE-SORT）是利用完全二叉树数据结构与归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略
时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$
稳定性：稳定

归并排序

//合并函数
void merge(vector<int> &ivec, vector<int> &tmp, int left, int mid, int right) {
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right){
        if (ivec[i] <= ivec[j]) tmp[k++] = ivec[i++];
        if (ivec[i] > ivec[j]) tmp[k++] = ivec[j++];
    }
    while (i <= mid) tmp[k++] = ivec[i++];
    while (j <= right) tmp[k++] = ivec[j++];
    for (int n = 0; n < k; n++) ivec[left + n] = tmp[n];
}
vector<int> MergeSort::sort(vector<int> ivec) {
    vector<int> tmp = ivec;
    int left = 0;
    int right = ivec.size()-1;
    mergeSort(ivec, tmp, left, right);
    return ivec;
}

//非递归
//以间隔为1开始进行归并，也就是(1,2),(3,4)依次分别进行归并
//以间隔2开始进行归并，也就是(1,2,3,4),(5,6,7,8)依次进行归并
//再以间隔2*2开始进行归并，直到全部排完
 void  mergeSort(vector<int> &ivec, vector<int> &tmp){
        int i = 1, length = ivec.size();
        while(i < length){
            int l = 0;
            while(l < length){
                mid = l + i - 1;
                r = min(l+ 2*i -1, length-1);
                if mid < r and mid < length:
                    merge(ivec, tmp, l, mid, r);
                l += 2*i;
            }
            i *= 2;
      }
}

//递归结构
void mergeSort(vector<int> &ivec, vector<int> &tmp, int left, int right) {
    if (left >= right) { return; }
    int mid = (left + right) / 2;
    mergeSort(ivec, tmp, left, mid);
    mergeSort(ivec, tmp, mid + 1, right);
    merge(ivec, tmp, left, mid, right);
}

计算机经典排序算法——C++实现

1.直接插入排序

2.冒泡排序

3.快速排序

4.选择排序

5.堆排序

6.归并排序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读