排序算法总结（C++）

发表于 | 分类于

常见C++排序算法图

1，直接插入

​ 插入排序的时间复杂度最好的情况是已经是正序的序列，只需比较(n-1)次，时间复杂度为O(n)，最坏的情况是倒序的序列，要比较n(n-1)/2次，时间复杂度为O(n^2 ) ，平均的话要比较时间复杂度为O(n^2 )

​ 插入排序是一种稳定的排序方法，排序元素比较少的时候很好，大量元素便会效率低下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertSort2(vector<int> &num)
{
    for(int i = 1;i < num.size();++i)
    {
        for(int j = i;j > 0;--j)
        {
            if(num[j] < num[j - 1])
            {
                int temp = num[j];
                num[j] = num[j-1];
                num[j-1] = temp;
            }
        }
    }
}

​

​

2，希尔排序

​ 希尔排序（ShellSort ）是插入排序的一种，是对直接插入排序算法的 改进该方法又称为缩小增量
排序。比较相距一定间隔的元素，即形如L[i,i+d,i+2d,…,i+kd]的序列然后缩小间距，再对各分组序列进行排序。直到之比较相邻元素的最后一趟排序为止，即最后的间距为1。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void ShellSort(vector<int> & nums){
    int n = nums.size();
    int i, j, tmp;
    int  d = n / 2;
    while (d >= 1){
    //对每组进行直接插入排序
        for (int i = d; i < n; ++i){
            tmp = nums[i];
            for (j = i - d; j >= 0 && tmp < nums[j]; j -= d){
                nums[j + d] = nums[j];
            }
            nums[j + d] = tmp;

        }
        d /= 2;
    }
}

3，直接选择

​ 对要排序的序列，选出关键字最小的数据，将它和第一个位置的数据交换，接着，选出关键字次小的 数据，将它与第二个位置上的数据交换。以此类推，直到完成整个过程 ，所以如果有n个数据，那么则需要遍历n-1遍。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectSort(vector<int> &nums){
    int n = nums.size();
    //只需n-1个位置需要考察，因为最后一个自然而然就放上了
    for (int i = 0; i < n - 1; i++){
        //每一趟我都是要去找最小的那个的序号
        int minx = nums[i];
        int cur = i;
        for (int j = i+1; j < n; j++){
            if (minx > nums[j]){
                cur = j;
            }
        }
        //交换
        swap(nums[cur], nums[i]);
    }
}

4，堆排序

​ 将数组A创建为一个最大堆，然后交换堆的根(最大元素)和最后一个叶节点x，将x从堆中去掉形成新的堆A1，然后重复以上动作，直到堆中只有一个节点。

​ 堆排序的时间复杂度是O(nlgN)，与快速排序达到相同的时间复杂度。但是在实际应用中，我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现，往往比堆排序具有更好的表现。堆排序的主要用途，是在形成和处理优先级队列方面。另外，如果计算要求是类优先级队列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同样是很适合的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//堆排序
void HeapSort(int arr[],int len){
    int i;
    //初始化堆，从最后一个父节点开始
    for(i = len/2 - 1; i >= 0; --i){
        Heapify(arr,i,len);
    }
    //从堆中的取出最大的元素再调整堆
    for(i = len - 1;i > 0;--i){
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //调整成堆
        Heapify(arr,0,i);
    }
}
//再看 调整成堆的函数

void Heapify(int arr[], int first, int end){
    int father = first;
    int son = father * 2 + 1;
    while(son < end){
        if(son + 1 < end && arr[son] < arr[son+1]) ++son;//存在右子节点就取右子节点，否则取左子节点
        //如果父节点大于子节点则表示调整完毕
        if(arr[father] > arr[son]) break;
        else {
         //不然就交换父节点和子节点的元素
            int temp = arr[father];
            arr[father] = arr[son];
            arr[son] = temp;
            //父和子节点变成下一个要比较的位置
            father = son;
            son = 2 * father + 1;
        }
    }
}

5，冒泡排序

​ 比较相邻的元素，如果反序则交换，过程也是分为有序区和无序区，初始时有序区为空，所有元素都在无序区，经过第一趟后就能找出最大的元素，然后重复便可

1
2
3
4
5
6
7
8
9
10
11
12
void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

6，快速排序

​ 快速排序首先选一个轴值(pivot，也有叫基准的)，将待排序记录划分成独立的两部分，左侧的元素均小于轴值，右侧的元素均大于或等于轴值，然后对这两部分再重复，直到整个序列有序

​ 过程是和二叉搜索树相似，就是一个递归的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
QuickSort(int arr[], int first, int end){
 int pivot = OnceSort(arr,first,end);
 //已经有轴值了，再对轴值左右进行递归
 QuickSort(arr,first,pivot-1);
 QuickSort(arr,pivot+1,end);
}

//接下来就是一次排序的函数
void OnceSort(int arr[], int first, int end){
 int i = first,j = end;
 //当i<j即移动的点还没到中间时循环
 while(i < j){
  //右边区开始，保证i<j并且arr[i]小于或者等于arr[j]的时候就向左遍历
  while(i < j && arr[i] <= arr[j]) --j;
  //这时候已经跳出循环，说明j>i 或者 arr[i]大于arr[j]了，如果i<j那就是arr[i]大于arr[j]，那就交换
  if(i < j){
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
  //对另一边执行同样的操作
  while(i < j && arr[i] <= arr[j]) ++i;
  if(i < j){
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 //返回已经移动的一边当做下次排序的轴值
 return i;
}

7，归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Merge(int arr[], int reg[], int start, int end) {
    if (start >= end)return;
    int len = end - start, mid = (len >> 1) + start;

    //分成两部分
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    //然后合并
    Merge(arr, reg, start1, end1);
    Merge(arr, reg, start2, end2);


    int k = start;
    //两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较
    //如此反复,可以把两个有序的序列合并成一个有序的序列
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];

    //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环
    //那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放
    while (start1 <= end1)
        reg[k++] = arr[start1++];

    //这一步和上面一样
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    //把已经有序的reg序列放回arr序列中
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void MergeSort(int arr[], const int len) {
    //创建一个同样长度的序列,用于临时存放
    int  reg[len];
    Merge(arr, reg, 0, len - 1);
}

8，基数排序

​ 它是一种非比较排序。它是根据位的高低进行排序，也就是先按照个位排序然后按照十位
排序……依次类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*基数排序*/
void RadixSort(vector<int> &array)
{
    int size = array.size();
    int bucket[10][10] = { 0 };//定义基数桶  
    int order[10] = { 0 };//保存每个基数桶之中的元素个数  
    int key_size = KeySize(array);//计算关键字位数的最大值  

    for (int n = 1; key_size>0; n *= 10, key_size--)
    {
        /*将待排序的元素按照关键值的大小依次放入基数桶之中*/
        for (int i = 0; i<size; i++)
        {
            int lsd = (array[i] / n) % 10;
            bucket[lsd][order[lsd]] = array[i];
            order[lsd]++;
        }

        /*将基数桶中的元素重新串接起来*/
        int k = 0,i;
        for (i = 0; i<10; i++)
        {
            if (order[i] != 0)
            {
                for (int j = 0; j<order[i]; j++)
                {
                    array[k] = bucket[i][j];
                    k++;
                }
                order[i] = 0;
            }
        }
    }
}

int main(){
    vector<int> nums{25,54,34,922,134,778};
    RadixSort(nums);
    for (auto a : nums){
        cout << a << " ";
    }
    cout << endl;
    return 0;

}