常用排序算法

插入：
直接插入。前有序后无序，有序依此插无序。
交换：
直接交换。前有序后无序，无序min 入有序。
冒泡交换。前无序后有序。无序max 入有序。
快排。设标兵，挖坑，填坑。使左边都比标兵小，右边都比标兵大。

归并：翻倍每次排序量，初始为2。
shell：缩小增量。初始增量n/2。

堆排序：取前n，建大根堆，交换根与叶子最右。取前n-1再建堆。

直插，冒泡，归并稳定。
堆，归并，快排，nlogn。

插入排序----直接插入

//插入排序  遍历无序序列，将无序元素插入有序序列中
void insert_sort(vector<int> a)
{
    int tmp;
    for(int i=1;i<a.size();i++)
    {
        tmp = a[i];

        int j = i-1;  //前j个是已排好序的
        //遍历【0】 [j]   [j+1]已保存，可用
        //与已排序的数逐一比较，大于temp时，该数移后
        while( j>=0 && a[j]>tmp )
        {
            a[j+1] = a[j];
            j--;
        }
        // a[1] = a[0];
        // 此时 j = -1；
        a[++j] = tmp;
    }

    for(auto i:a)
        cout << i <<",";
}

选择排序----简单选择

// 选择排序    遍历a[1]-a[n] 交换，使a[0]为min
// 每次选最小的 5 8 5 2 9    2和5交换 前5 变 后5 不稳定
void choose_sort(vector<int> a)
{
    for(int i=0;i<a.size()-1;i++)
    {
        int min = a[i];
        for(int j=i; j<a.size(); j++)
        {
            if(a[j] < a[i])  // == 时顺序不变 所以稳定;
            {
                swap(a[i],a[j]);
            }
        }
    }
    for(auto i:a)
    {
        cout << i <<",";
    }
}

交换排序----冒泡排序

// 冒泡  稳定   交换相邻两数,  使max在最后
// 每一躺，在前面的无序中 冒一个max到最后
void bubbling_sort(vector<int> a)
{
    for(int i=0;i<a.size()-1;i++)
    {
        for(int j=0; j<a.size()-1-i; j++)
        {
            if(a[j] > a[j+1])  // == 时顺序不变 所以稳定;
            {
                swap(a[j],a[j+1]);
            }
        }
    }
    for(auto i:a)
    {
        cout << i <<",";
    }
    cout <<endl;
}

交换排序----快速排序

#include <iostream>
using namespace std;

void quick_sort(int a[],int l,int r)
{
    int tmp = a[l];
    int hole = l;       //坑在a[l]上
    int left  = l;
    int right = r;
    while(left < right)
    {
        while(a[right] > tmp && left < right)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;   //坑的位置
        while(a[left] < tmp && left <right)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;   //坑的位置
    }
    //此时left == right == hole 填坑
    a[hole] = tmp;

    if(l < hole-1)
    {
        quick_sort(a, l, hole-1);
    }
    if(hole+1 < r)
    {
        quick_sort(a, hole+1, r);
    }
}


int main()
{
    int a[10] = {4,3,2,1,0,9,8,7,6,5};
    quick_sort(a,0,9);
    for(int i=0; i<10; i++)
    {
        cout << a[i] << endl;
    }
    return 0;
 }

归并排序

//归并排序
//初始状态：6,202,100,301,38,8,1
//第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
//第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
//第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
//总的比较次数为：3+4+4=11；
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}

//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

希尔排序

//希尔排序 缩小增量排序
// 增量:: 相隔较远两数的距离
// 增量:  sum = 10 5,2,1  sum = 11 5,2,1 tag
void shell_sort(int a[], int len)
{
    for(int gap=len/2; gap>0; gap=gap/2)
    {
        for (int i=gap; i<len; i++)
        {
//              for(int j=i-gap; j>=0; j=j-gap)
//              {
//                  if(a[j]>a[j+gap])     // a[j] > a[j+gap] 时跳出for还是继续 j = j-gap
//                  {
//                    int temp = a[j];    // 实际上tag值一定时 只有一次a[j]<a[j+gap]  之前的 必然都小
//                    a[j] = a[j+gap];
//                    a[j+gap] = temp;
//                  }
//                  else{
//                      break;
//                  }
//              }
            for(int j=i-gap; j>=0 && a[j]>a[j+gap]; j=j-gap)
            {
                int temp = a[j];
                a[j] = a[j+gap];
                a[j+gap] = temp;
            }
        }
    }
    for(int i=0;i<len;i++)
    {
        printf("%dn",a[i]);
    }
}

shell排序如下图 当a[j]>a[j+gap] //3<9 3之前gap为2的数必然是递增的，不必再执行最里层的for循环

堆排序

//堆排序
//建堆
// 假设已经有了n个数据，那么新数据自然放在n位（因为位置是从0开始）
// 将新数据与 (n-1)/2 位置的数据（新数据的父节点）比较，如果比父节点大，那么就交换，继续比较，直到它比父节点小。 就插入完成
// 依此插入 完成建堆
void make_heap_c(int a[], int len)
{
    for(int i=0; i<len; i++)
    {
        int j = i;
        while( (j-1)/2 >= 0)    //父亲存在
        {
            int son = a[j];     //当前节点
            int fa = a[(j-1)/2];    //父节点
            if(fa >= son)
                break;
            else{
                int tmp = a[j];
                a[j] = a[(j-1)/2];
                a[(j-1)/2] = tmp;
                j = (j-1)/2;        //令当前节点为 父节点 向上遍历
            }
        }
    }
}
void heap_sort_c(int a[], int size)
{
    for(int i=0; i<size-1; i++)
    {
        make_heap_c(a, size-i);       //  前 size-i 位  造 大根堆
        int tmp = a[0];
        a[0] = a[size -i -1];
        a[size -i -1] = tmp;
    }
    for(int i=0; i<size; i++)
    {
        printf("%d,",a[i]);
    }
}

c++ make_heap()实现堆排序

void heap_sort(vector<int>& a)
{
    vector<int>::iterator it1 = a.begin();
    vector<int>::iterator it2 = a.end();
    for(int i=0; i<a.size()-1; i++)
    {
        make_heap(it1, it2);       //大根堆
        int  m= *it1;
        *it1 = *(it2-1);           //   取范围时[), 取值时it2要减1
        *(it2-1) = m;
        it2--;
    }
    for(auto tmp:a)
        cout << tmp << endl;
}

最后

以上就是激情夏天为你收集整理的常用排序算法的全部内容，希望文章能够帮你解决常用排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。