您的位置: 首页  >  文章  >  各大排序算法C++代码实现

各大排序算法C++代码实现

分类: 文章 • 2023-11-18 09:12:28

 排序算法分类

各大排序算法C++代码实现

 排序算法比较表格

各大排序算法C++代码实现

 注：

1 归并排序可以通过手摇算法将空间复杂度降到O（1），但是时间复杂度会提高。
2 基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数。

辅助记忆

---- 时间复杂度记忆- 

  • 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(各大排序算法C++代码实现)O(各大排序算法C++代码实现)（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
  • 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）

---- 稳定性记忆-“快希选堆”（快牺牲稳定性） 

关于所有排序的动画请参考：https://visualgo.net/en/sorting

【代码实现】

1 冒泡排序

//array[]为待排序数组，n为数组长度
void BubbleSort(int array[], int n)
{
    int i, j, k;
    for(i=0; i<n-1; i++)
        for(j=0; j<n-1-i; j++)
        {
            if(array[j]>array[j+1])
            {
                k=array[j];
                array[j]=array[j+1];
                array[j+1]=k;
            }
        }
}

2.选择排序

#include <iostream>
#include<string>
using namespace std;
 
void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
 
void selectSort(int a[], int n)
{
    for(int i=0;i<n;++i)
    {
        int index=i;
        for(int j=i+1;j<n;++j)
        {
            if(a[j]<a[index])
                index=j;
        }
        swap(a[index],a[i]);
        print(a,n,i);
    }
    
}
 
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    selectSort(a,8);
    print(a,8,8);
}

3.插入排序

#include <iostream>
 
using namespace std;
 
void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
 
 
void InsertSort(int a[], int n)
{
    for(int i=1;i<n;i++)
    {
        int value=a[i];
        int index=i-1;
        while(index>=0&&a[index]>value)
        {
            a[index+1]=a[index];
            index--;
        }
        a[index+1]=value;
        print(a,n,i);
    }
}
 
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    InsertSort(a,8);
    print(a,8,8);
}

4.归并排序

  • 递归实现
#include<iostream>
 
using namespace std;
 
void Merge(int arr[], int l, int q, int r){
    int n=r-l+1;//临时数组存合并后的有序序列
    int* tmp=new int[n];
    int i=0;
    int left=l;
    int right=q+1;
    while(left<=q && right<=r)
        tmp[i++] = arr[left]<= arr[right]?arr[left++]:arr[right++];
    while(left<=q)
        tmp[i++]=arr[left++];
    while(right<=r)
        tmp[i++]=arr[right++];
    for(int j=0;j<n;++j)
        arr[l+j]=tmp[j];
    delete [] tmp;//删掉堆区的内存
}
 
void MergeSort(int arr[], int l, int r){
    if(l==r)
        return;  //递归基是让数组中的每个数单独成为长度为1的区间
    int q = (l + r)/2;
    MergeSort(arr, l, q);
    MergeSort(arr, q + 1, r);
    Merge(arr, l, q, r);
    
}
 
int main(){
    int a[8] = {3,1,2,4,5,8,7,6};
    MergeSort(a,0,7);
    for(int i=0;i<8;++i)
        cout<<a[i]<<" ";
}
  • 迭代实现
#include<iostream>
#include<vector>
 
using namespace std;
 
// 区间[head1, head2-1]和[head2, tail2]都是排好序的，现在需要合并
void mergeSortHelper(vector<int>& v, int head1, int head2, int tail2) {
    int tail1 = head2 - 1, index = 0, len = tail2 - head1 + 1, start = head1;
    vector<int> tmp(len);
    while (head1 <= tail1 || head2 <= tail2) {
        if (head1 > tail1)
            tmp[index++] = v[head2++];
        else if (head2 > tail2)
            tmp[index++] = v[head1++];
        else {
            if (v[head1] <= v[head2])
                tmp[index++] = v[head1++];
            else
                tmp[index++] = v[head2++];
        }
    }
    
    for (int i = 0; i < len; ++i)
        v[start+i] = tmp[i];
}
 
void mergeSort(vector<int>& v) {
    int len = v.size();
    // 倍进枚举步长1,2,4,……
    for (int step = 1; step <= len; step <<= 1) {
        int offset = step + step;
        for (int index = 0; index < len; index += offset)
            mergeSortHelper(v, index, min(index+step, len-1), min(index+offset-1, len-1));
    }
}
 
int main(){
    vector<int> a = {3,1,2,4,5,8,7,6};
    mergeSort(a);
    for(int i=0;i<8;++i)
        cout<<a[i]<<" ";
}

5.快速排序 

#include<iostream>
 
using namespace std;
 
int Parition(int a[], int low,int high){
    int pivot=a[high];
    int i=low;
    for(int j=low;j<high;++j)
    {
        //j指向当前遍历元素，如果大于等于pivot，继续向前
        //如果小于当前元素，则和i指向的元素交换
        if (a[j]<pivot) {
            swap(a[j], a[i]);
            i++;
        }
    }
    swap(a[i], a[high]);
    return i;
    
}
 
void QuickSort(int a[], int low, int high){
    if(low<high)
    {
        int q=Parition(a,low, high);
        QuickSort(a, low, q-1);
        QuickSort(a, q+1,high);
        
    }
    
}
 
int main(){
    int a[8] = {3,1,2,4,5,8,7,6};
    QuickSort(a,0,7);
    for(int i=0;i<8;++i)
        cout<<a[i]<<" ";
}

 6.堆排序

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//建堆函数,该函数是堆排序的实现重点
void Maxheap(int arr[], int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        Maxheap(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }
    
}
void heapSort(int arr[], int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        Maxheap(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        Maxheap(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}
 
int main()
{
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for(auto it: array)
    {
        cout<<it<<endl;
    }
    return 0;
}

7.希尔排序 

#include<iostream>
 
using namespace std;
const int INCRGAP = 3;
void shellSort(int a[],int len)
{
    int insertNum = 0;
    unsigned gap = len/INCRGAP + 1; // 步长初始化,注意如果当len<INCRGAP时，gap为0，所以为了保证进入循环，gap至少为1！！！
    while(gap) // while gap>=1
    {
        for (unsigned i = gap; i < len; ++i) // 分组，在每个子序列中进行插入排序
        {
            insertNum = a[i];//将当前的元素值先存起来方便后面插入
            unsigned j = i;
            while (j >= gap && insertNum < a[j-gap])//寻找插入位置
            {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = insertNum;
        }
        gap = gap/INCRGAP;
    }
}
int main()
{
    int array[11] = {2, 1, 4, 3, 11, 6, 5, 7, 8, 10, 15};
    shellSort(array, 11);
    for(auto it: array)
    {
        cout<<it<<endl;
    }
    return 0;
}

 

相关推荐