C++实现十大排序算法及排序算法常见问题

目录
  • 前言
  • 0 概述
  • 1 冒泡排序
  • 2 选择排序
  • 3 插入排序
  • 4 希尔排序
  • 5 归并排序
  • 6 堆排序
  • 7 快速排序
  • 8 计数排序
  • 9 桶排序
  • 10 基数排序
  • 总结

前言

本文为C++实现的十大排序算法及基于排序算法解决的一些常见问题,每一种算法均实际运行,确保正确无误。文中内容为自己的一些理解,如有错误,请大家指正。

0 概述

在十种排序算法中,前七种是比较类排序,后三种是非比较类排序,每种算法的最好、最坏、平均时间复杂度,空间复杂度以及稳定性如下表所示。稳定性是指排序前后相等的元素相对位置保持不变。

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n²) O(n) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n) O(n²) O(1) 稳定
希尔排序 O(nlogn) O() O(n²) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n + logn) 稳定
堆排序 O(nlogn) O(nlogn) O(n²) O(logn) 不稳定
快速排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n + k) O(n + k) O(n²) O(n + k) 稳定
桶排序 O(n + k) O(n + k) O(n + k) O(k) 稳定
基数排序 O(n × k) O(n × k) O(n × k) O(n + k) 稳定

具体思路和代码均为升序排序。

前三种排序比较类似,都是将数组划分成已排序部分未排序部分,因此有两层循环,一层循环划分已排序和未排序部分的边界,一层循环选择不同的方法依次对未排序的部分进行排序。

1 冒泡排序

顾名思义,冒泡排序(bubble sort)是将最大的数依次 “上浮” 到数组的末尾,实现数组有序。

具体的算法实现原理:

两层循环,第一层划分边界,从后向前,后面部分为已排序部分。第二层循环从最前往后(截止到边界)依次两两比较,如果前面的数比后面的数大,则交换两个数,如果前面的数比后面的数小,则保持不变。当边界移动到第一个数,数组实现有序。

动态图解:

代码:

#include <iostream>
#include <vector>
using namespace std;

//冒泡排序
void bubbleSort(vector<int> &vec){
    int len = vec.size();
    if (len <= 1){
        return;
    }
    for (int i = len -1; i > 0; i--){
        bool flag = false;  //使用flag判断j前面的子序列是否已经有序
        for (int j = 0; j < i; j++){
            if (vec[j] > vec[j + 1]){
                swap(vec[j], vec[j + 1]);
                flag = true;
            }
        }
        if (!flag){
            break;
        }
    }
}

//打印数组
void printVec(vector<int> vec){
    for (auto c : vec){
        cout << c << " ";
    }
    cout << endl;
}

//test
int main(){
    vector<int> test_vec = {1, 2, 5, 7, 3, 5, 9, 33, 44, 99, 55};
    printVec(test_vec);
    bubbleSort(test_vec);
    printVec(test_vec);
    system("pause");
    return 0;
}

2 选择排序

具体的算法实现原理:

选择排序(selection sort)已排序部分为数组的前部,然后选择数组后部未排序中的最小的数依次与未排序的第一个数交换(交换会造成排序不稳定),然后边界后移,继续选择、交换,直到数组有序。

两层循环,第一层划分边界,第二层循环查找未排序部分最小的数,并与未排序部分的第一个数交换。

动态图解:

代码:

#include <iostream>
#include <vector>
using namespace std;

//选择排序
void selectSort(vector<int> &vec){
    int len = vec.size();
    if (len <= 1){
        return;
    }

    for (int i = 0; i < len; i++){
        int min = i;
        for (int j = i; j < len; j++){
            if (vec[j] < vec[min]){
                min = j;
            }
        }
        swap(vec[i], vec[min]);
    }
}

//打印数组
void printVec(vector<int> vec){
    for (auto c : vec){
        cout << c << " ";
    }
    cout << endl;
}

//test
int main(){
    vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55};
    printVec(test_vec);
    selectSort(test_vec);
    printVec(test_vec);
    system("pause");
    return 0;
}

3 插入排序

具体的算法实现原理:

插入排序(insertion sort)已排序部分也为数组的前部,然后将未排序部分的第一个数插入到已排序部分的合适的位置。

两层循环,第一层划分边界,第二层循环将已排序部分的数从后向前依次与未排序部分的第一个数比较,若已排序部分的数比未排序部分的第一个数大则交换,这样未排序部分的第一个数就插入到已排序部分的合适的位置,然后向后移动边界,重复此过程,直到有序。

动态图解:

代码:

#include <iostream>
#include <vector>
using namespace std;

//插入排序
void insertSort(vector<int> &vec){
    int length = vec.size();
    if (length <= 1){
        return;
    }
    for (int i = 1; i < length - 1; i++){
        //int temp = vec[i];
        for (int j = i - 1; j >= 0; j--){
            if (vec[j] > vec[j + 1]){
                swap(vec[j+1], vec[j]);
            }
        }
    }
}

//打印数组
void printVec(vector<int> vec){
    for (auto c : vec){
        cout << c << " ";
    }
    cout << endl;
}

//test
int main(){
    vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9};
    printVec(test_vec);
    insertSort(test_vec);
    printVec(test_vec);
    system("pause");
    return 0;
}

4 希尔排序

希尔排序是插入排序的升级,算法原理如下:

1) 首先,从数组的首元素开始每隔“步长(间隔)”个元素就挑选一个元素出来作为子数组元素;

2) 然后每个子数组各自进行比较,比较好后,每个子数组都有顺序,进入下一轮,步长(间隔)减少,再根据步长(间隔)分组进行比较;

3) 重复以上操作,最后就有序了。

图解:

代码:

#include <iostream>
#include <vector>
using namespace std;

//希尔排序
void shellSort(vector<int> &vec){
    int len = vec.size();
    if (len <= 1) return;
    //以h为步长划分数组,h /= 2为缩小的增量,数字2可自己根据数据选择
    for (int h = len / 2; h > 0; h /= 2){
        //以下为插入排序
        for (int j = h; j < len; j++){
            int temp = vec[j];
            for (int k = j - h; k >= 0; k -= h){
                if (vec[k] > temp){
                    swap(vec[k], vec[k + h]);
                }
            }
        }
    }
}

//打印数组
void printVec(vector<int> vec){
    for (auto c : vec){
        cout << c << " ";
    }
    cout << endl;
}

//test
int main(){
    vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55};
    printVec(test_vec);
    shellSort(test_vec);
    printVec(test_vec);
    system("pause");
    return 0;
}

5 归并排序

归并排序(Merge Sort)是分治思想的一个典型应用,如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了(前后两部分也采用相同的方法排序,即将前后两部分分别再从中间分成两部分排序后合并,以此类推,直到数组不可再分)。因此,归并排序是一个先分再合的过程,用到的思想为分治,具体实现方式为递归

下面的图解很清晰的说明了归并排序的原理。

现在弄清楚原理了,但还有一个问题没有解决:如何合并两个排好序的前后数组?答案很简单,双指针 + 临时数组。指针P1指向前面数组的首元素,指针P2指向后面数组的首元素,比较大小,将较小的元素放在临时数组helper中,然后将指向较小元素的指针后移,再次比较,将较小的元素放入临时数组。如此反复,直到前后两个数组中的某个指针到达边界,然后将未到达边界的数组剩余的元素放入临时数组尾部,合并完成。最后将合并好的元素拷贝到原数组。

具体代码如下:

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int> &vec, int left, int right);
void merge(vector<int> &vec, int left, int mid, int right);
void printVec(vector<int> vec);

//test
int main(){
    vector<int> test_vec = {1, 5, 2, 7, 23, 5, 9, 33, 44, 99, 55};
    printVec(test_vec);
    mergeSort(test_vec, 0, test_vec.size() - 1);
    printVec(test_vec);
    system("pause");
    return 0;
}

//归并排序,先分再合
void mergeSort(vector<int> &vec, int left, int right){
    if (left >= right){
        return;
    }
    //int mid = left + (right - left) / 2;
    int mid = left + ((right - left) >> 1);  

    mergeSort(vec, left, mid);
    mergeSort(vec, mid + 1, right);
    merge(vec, left, mid, right);  //合并
}

//合并,双指针 + 临时数组
void merge(vector<int> &vec, int left, int mid, int right){
    int n = right - left + 1;
    vector<int> helper(n, 0); //临时数组
    int i = 0;
    int p1 = left;  //第一个指针
    int p2 = mid + 1;  //第二个指针
    //在两个指针都没有越过边界的情况下,将两个数组中较小的数放入临时数组,并将指针后移
    while (p1 <= mid && p2 <= right){
        helper[i++] = vec[p2] < vec[p1] ? vec[p2++] : vec[p1++];
    }
    //将未到达边界的数组的剩余元素拷贝到临时数组尾部
    while (p1 <= mid){
        helper[i++] = vec[p1++];
    }
    while (p2 <= right){
        helper[i++] = vec[p2++];
    }
    //将临时数组的元素拷贝到原数组
    for (int j = 0; j < n; j++){
        vec[left + j] = helper[j];
    }
}

//打印数组
void printVec(vector<int> vec){
    for (auto c : vec){
        cout << c << " ";
    }
    cout << endl;
}
 

6 堆排序

堆排序(Heap Sort)的思路步骤为(假设数组共有n个元素):将待排序数组构造成一个大顶堆,此时,整个数组的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个大顶堆,这样会得到n个元素的次小值,再次交换堆顶元素和第n-1个元素,这样倒数后两个数为最大的两个数且有序。如此反复执行,便能得到一个有序数组了。

动态图解:

简化一下:①构建大顶堆 → ②交换元素 → ③重构大顶堆 → ④交换元素 → 循环③④ 步

具体代码如下:

#include <iostream>
#include <vector>
using namespace std;

void heapSort(vector<int> &vec);
void heapInsert(vector<int> &vec, int index);
void heapify(vector<int> &vec, int index, int len);
void print_vec(vector<int> vec);

int main(){
    vector<int> test_vec = {3, 1, 4, 6, 2, 7, 5, 8, 2, 12};
    int len = test_vec.size();
    print_vec(test_vec);
    heapSort(test_vec);
    print_vec(test_vec);
    system("pause");
    return 0;
}

//堆排序
void heapSort(vector<int> &vec){
    int len = vec.size();

    if (len <= 1){
        return;
    }

    //构建大顶堆
    for (int i = 0; i < len; i++){
        heapInsert(vec, i);
    }

    //交换堆顶元素和末尾元素
    swap(vec[0], vec[--len]);

    //循环,重构大顶堆,交换元素
    while (len > 0){
        heapify(vec, 0, len);
        swap(vec[0], vec[--len]);
    }
}

//index的父节点为(index - 1) / 2
void heapInsert(vector<int> &vec, int index){
    while (vec[index] > vec[(index - 1) / 2]){
        swap(vec[index], vec[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

//重构[index, len)的区间为大顶堆
void heapify(vector<int> &vec, int index, int len){
    int leftson = index * 2 + 1; //index的左子节点,leftson + 1为右子节点
    while(leftson < len){
        int largest = (leftson + 1 < len && vec[leftson+ 1] > vec[leftson]) ? leftson + 1 : leftson;
        largest = vec[largest] > vec[index] ? largest : index;
        if (largest == index){
            break;
        }
        swap(vec[index], vec[largest]);
        index = largest;
        leftson = index * 2 + 1;
    }
}

//打印数组
void print_vec(vector<int> vec){
    for (auto c : vec){
        cout << c <<" ";
    }
    cout << endl;
}

7 快速排序

快速排序(Quick Sort)也用到了分治思想,如果要排列下标从 left 到 right 的数组,我们可以选择从 left 到 right 之间的任意一个元素作为分区点P,然后遍历从 left 到 right 的元素,将小于等于分区点P的数放在左边,大于分区点P的数放在右边,将分区点P放在中间。然后使用相同的方法将小于等于分区点P的数划分成三部分,将大于分区点P的数分成三部分。依次类推,直到数组不可再分,则整个数组实现有序。因此,快速排序用到的思想为分治,具体实现方式为递归

动态图解(该图解是将最后一个数最为分区点,借助这个图也可以理解将随机选取的数作为分区点):

与归并排序一样,理解了原理之后,还有一个问题没有解决:如何根据随机选取的数来分区(partition)?答案是借助指针来分界。我们设置两个指针,指针small为小于等于分区点P的数边界,指针P为

8 计数排序

思路:

  • 遍历待排序数组A,找出其最小值min和最大值max;
  • 创建一个长度为max-min+1的数组B,其所有元素初始化为0,数组首位对应数组A的min元素,索引为i位置对应A中值为min+i的元素;
  • 遍历数组A,在B中对应位置记录A中各元素出现的次数;
  • 遍历数组B,按照之前记录的出现次数,输出几次对应元素;

稳定性解释: 稳定排序算法;

代码:

// 计数排序
void count_Sort(vector<int>& array)
{
    if (array.empty()){
        return;
    }
    //找出最大最小值
    int min = array.front(),max = array.front();
    for (int i = 1; i < array.size(); i++)
    {
        if (min > array[i])
        {
            min = array[i];
        }
        else if (max < array[i])
        {
            max = array[i];
        }
    }

    // 记录各元素出现次数
    vector<int> counts(max - min + 1);
    for (int i = 0; i < array.size(); i++)
    {
        counts[array[i] - min]++;
    }

    // 根据记录的次数输出对应元素
    int index = 0;
    for (int j = 0; j < counts.size(); j++)
    {
        int n = counts[j];
        while (n--){
            array[index] = j + min;
            index++;
        }
    }
}

9 桶排序

思路:

  • 设置固定数量的空桶;
  • 找出待排序数组的最大值和最小值;
  • 根据最大最小值平均划分各桶对应的范围,并将待排序数组放入对应桶中;
  • 为每个不为空的桶中数据进行排序(例如,插入排序);
  • 拼接不为空的桶中数据,得到排序后的结果。

稳定性解释: 常见排序算法中最快的一种稳定算法;可以计算大批量数据,符合线性期望时间;外部排序方式,需额外耗费n个空间;

代码:

// 桶排序
void bucketSort (vector<int>& array, int bucketCount)
{
    if (array.empty())
    {
        return;
    }
    // 找出最大最小值
    int max = array.front(), min = array.front();
    for (int i = 1; i < array.size(); i++)
    {
        if (min > array[i])
        {
            min = array[i];
        }
        else if (max < array[i])
        {
            max = array[i];
        }
    }

    // 将待排序的各元素分入对应桶中
    vector<vector<int>> buckets(bucketCount);
    int bucketSize = ceil((double)(max - min + 1) / bucketCount);
    for (int i = 0; i < array.size(); i++)
    {
        int bucketIndex = (array[i] - min) / bucketSize;
        buckets[bucketIndex].push_back(array[i]);
    }

    // 对各桶中元素进行选择排序
    int index = 0;
    for (vector<int> bucket : buckets)
    {
        if (!bucket.empty())
        {
            // 使用选择排序算法对桶内元素进行排序
            selectSort(bucket);
            for (int value : bucket)
            {
                array[index] = value;
                index++;
            }
        }
    }

}
// 桶排序
void bucketSort (vector<int>& array)
{
    bucketSort (array, array.size() / 2);
}

10 基数排序

思路: 将各待比较元素数值统一数位长度,即对数位短者在前补零;根据个位数值大小,对数组进行排序;重复上一步骤,依次根据更高位数值进行排序,直至到达最高位;

稳定性解释: 稳定算法;适用于正整数数据(若包含负数,那么需要额外分开处理);对于实数,需指定精度,才可使用此算法。

代码:

// 基数排序,对array的left到right区段,按照curDigit位进行排序
void radixSortImprove(vector<int>& array, int left, int right, int curDigit)
 {
 if (left >= right || curDigit < 10)
 {
  return;
 }
 // 将各元素按当前位数值大小分入各桶
 vector<vector<int>> buckets(10);
 for (int i = left; i <= right; i++)
 {
  int bucketIndex = (array[i] % curDigit - array[i] % (curDigit / 10)) / (curDigit / 10);
  buckets[bucketIndex].push_back(array[i]);
 }

 // 按照桶的顺序,将桶中元素拼接
 // 对于元素个数大于1的桶,桶内元素按照更低位来进行排序
 int index = 0;
 for (vector<int> bucket : buckets)
 {
  int newLeft = index, newRight = index;
  for (int value : bucket)
  {
   array[index] = value;
   index++;
  }
  newRight = index - 1;
  radixSortImprove(array, newLeft, newRight, curDigit / 10);
 }
}
// 基数排序(从高位开始)
void radix_Sort(vector<int>& v)
{
 // 计算当前数组最大数位数
 int curDigit = 10;
 for (autovalue : v)
 {
  if (value / curDigit) {
   curDigit *= 10;
  }
 }
 radixSortImprove(array, 0, array.size() - 1, curDigit);
}

总结

到此这篇关于C++实现十大排序算法及排序算法常见问题的文章就介绍到这了,更多相关C++十大排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C/C++语言八大排序算法之桶排序全过程示例详解

    基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕. 首先我们要求出一个数组的最大数然后求出他的最大位数 //求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++

  • 简单掌握桶排序算法及C++版的代码实现

    桶排序介绍 桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里. 假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX).在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0:将容量为MAX的桶数组中的每一个单元都看作一个"桶". 在排序时,逐个遍历数组a,将数组a的值,作为"桶数组r"的下标.当a中数据被读取时,就将桶的值加1.例如,读取到数组a[3]=5,则将r[5]的值+1. C++实现算法 假设数

  • 详解C++ 桶排序(BucketSort)

    一.思路 是将[0,1]区间划分为n个等长的子区间.然后,将各个元素按照自己所属的区间放入相应的桶中,只需要将每个桶的元素排好序,依次输出各个桶内的元素,就得到了有序的元素序列. 二.实现程序: #include <iostream> using namespace std; const int offset = 105; // 为桶的边界 const int maxSize = 100; // 数组的最大存储范围 // 桶排序 template <typename T> void

  • C/C++实现八大排序算法汇总

    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1. 插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已

  • java版十大排序经典算法:完整代码

    目录 十大排序算法对比 冒泡排序 完整代码: 测试代码: 运行结果: 快速排序 完整代码: 总结 十大排序算法对比 关于最后一列的稳定性,我稍微解释下,例如对序列:1 2 4 2 6 排序,序列中存在两个2,如果我们把这两个2标记上(让他俩不同),排序之后,前面的2还在前面,那么就称这种排序是稳定的,反之不稳定. 冒泡排序 简单解释: 原理就如算法名字一样,就像水中的气泡一样,每次我都把最大的或最小的放到最后面,这样总共需要n-1趟即可完成排序,这就是第一层循环,第二次循环就是遍历未被固定的那些

  • java版十大排序经典算法:完整代码(4)

    目录 计数排序 完整代码: 桶排序 完整代码: 基数排序 完整代码: 完整测试类 总结 计数排序 简单解释:这个排序算法看名字也很好理解,就是就是额外找个数组来计数,然后在这个数组从小到大或从大到小把数取出来即可. 完整代码: package com.keafmd.Sequence; /** * Keafmd * * @ClassName: CountSort * @Description: 计数排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 11:31 */

  • Python 数据结构之十大经典排序算法一文通关

    目录 1.冒泡排序 算法演示 算法步骤 算法实现 2.选择排序 算法演示 算法步骤 算法实现 3.简单插入排序 算法演示 算法步骤 算法实现 4.希尔排序 算法演示 算法步骤 算法实现 5.归并排序 算法演示 算法步骤 算法实现 6.快速排序 算法演示 算法步骤 算法实现 7.堆排序 算法演示 算法步骤 算法实现 8.计数排序 算法演示 算法步骤 算法实现 9.桶排序 算法演示 算法步骤 算法实现 10.基数排序 算法演示 算法步骤 算法实现 一文搞掂十大经典排序算法 今天整理一下十大经典排序算

  • Java 十大排序算法之冒泡排序刨析

    目录 冒泡排序原理 冒泡排序API设计 冒泡排序的代码实现 冒泡排序的时间复杂度分析 冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值 冒泡排序API设计 类名 Bubble 构造方法 Bubble:创建Bubble对象 成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C

  • Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

  • Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • Java 十大排序算法之归并排序刨析

    目录 归并排序原理 归并排序API设计 归并排序代码实现 归并排序的时间复杂度分析 归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计 类名 Merge 构造方法 Merge():创建Merge对象 成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行

  • Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

  • Java 十大排序算法之堆排序刨析

    二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ

  • Java 十大排序算法之计数排序刨析

    计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素 计数排序优缺点 优点:快 缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费 使用范围:数据较为密集或范围较小时适用. 思路 1.找出最大元素max 2.初始化一个max+1的数组 3.将每个元素的计数存储在数组中各自的索引处 4.存储计数数组元素的累积和 5.数组中找到原始数组的每个元素的索引 计数排序代码实现 public class CountingSort { private static

随机推荐