作家：billy 空姐 偷拍
简介排序算法不错分为里面排序和外部排序，里面排序是数据记载在内存中进行排序，而外部排序是因排序的数据很大，一次不成容纳一起的排序记载，在排序过程中需要造访外存。十大排序算法用一张图综合：
图片
一. 冒泡排序冒泡排序（Bubble Sort）是一种浅薄直不雅的排序算法。它重迭地走访过要排序的数列，一次相比两个元素，要是他们的规定诞妄就把他们交换过来。走访数列的职责是重迭地进行直到莫得再需要交换，也等于说该数列一经排序完成。这个算法的名字由来是因为越小的元素会经由交换冉冉“浮”到数列的尖端。冒泡排序还有一种优化算法，等于立一个 flag，当在一回序列遍历中元素莫得发生交换，则解释该序列一经有序。但这种修订关于栽植性能来说并莫得什么太大作用
1. 算法门径 1）相比相邻的元素。要是第一个比第二个大，就交换两个的位置2）对每一双相邻元素作念相同的职责，从动手第一双到斥逐的临了一双。这步作念完后，临了的元素会是最大的数3）针对总计的元素重迭以上的门径，除了临了一个4）抓续每次对越来越少的元素重迭上头的门径，直到莫得任何一双数字需要相比 2. 代码void BSortMethod::bubbleSort(int *vec， int len)
{
// 每次遍历找到最大的数放在最右边，临了一个数毋庸相比，是以一共进行 len - 1 次遍历
for ( int i = 1; i < len; ++i )
{
for ( int j = 0; j < len - i; ++j )
{
if ( vec[j] > vec[j+1] ) {
int temp = vec[j];
vec[j] = vec[j+1];
vec[j+1] = temp;
}
}
}
}
3. 服从展示
图片
二. 采用排序采用排序（Selection Sort）是一种浅薄直不雅的排序算法，岂论什么数据进去都是 O(n²) 的时分复杂度。是以用到它的技巧，数据畛域越小越好。独一的自制可能等于不占用至极的内存空间了吧
1. 算法门径 1）开首在未排序的序列中找到最小或最大的元素，存放到排序序列的肇端位置2）再从剩余未排序元素中络续寻找最小或最大的元素，然后放到已排序序列的末尾3）重迭第二步，直到总计元素均排序完结 2. 代码void BSortMethod::selectionSort(int *vec， int len)
{
for ( int i = 0; i < len - 1; ++i )
{
int minIndex = i;
// 每次遍历找到最小值的索引
for ( int j = i + 1; j < len; ++j )
{
if ( vec[j] < vec[minIndex] ) {
minIndex = j;
}
}
// 把最小值放在有序序列的临了
if ( minIndex != i ) {
int temp = vec[minIndex];
vec[minIndex] = vec[i];
vec[i] = temp;
}
}
}
图片
3. 服从展示
图片
三. 插入排序插入排序（Insertion Sort）的代码杀青天然莫得冒泡排序和采用排序那么浅薄泼辣，但它的旨趣应该是最容易贯通的了，因为唯独打过扑克牌的东谈主都应该好像秒懂。插入排序是一种最浅薄直不雅的排序算法，它的职责旨趣是通过构建有序序列，关于未排序数据，在已排序序列中从后上前扫描，找到相应位置并插入
呦女朱朱 1. 算法门径 1）把待排序序列的第一个元素看作念一个有序序列，把第二个元素到临了一个元素当成是未排序序列2）从新到尾挨次扫描未排序序列，将扫描到的每个元素插入有序序列的相宜位置。要是待插入的元素与有序序列中的某个元素额外，则将待插入元素插入到额外元素的背面 2. 代码void BSortMethod::insertionSort(int *vec， int len)
{
for ( int i = 0; i < len; ++i )
{
int preIndex = i - 1;
int currentValue = vec[i];
// 从后往前遍历有序列表，直到找到比现时数值小或者额外的数的索引，咱们在这个索引后插入 currentValue
while ( preIndex >= 0 && vec[preIndex] > currentValue )
{
vec[preIndex + 1] = vec[preIndex];
preIndex--;
}
vec[preIndex+1] = currentValue;
}
}
图片
3. 服从展示
图片
四. 希尔排序希尔排序（Shell Sort）空姐 偷拍，也称递减增量排序算法，是插入排序的一种更高效的修订版块。但希尔排序短长融会排序算法。 希尔排序是基于插入排序的以下两点性质而漠视修订门径的：
插入排序在对着实一经排好序的数据操作时，服从高，即不错达到线性排序的服从；但插入排序一般来说是低效的，因为插入排序每次只可将数据移动一位；希尔排序的基本想想是：先将通盘待排序的记载序列分割成为多少子序列分别进行平直插入排序，待通盘序列中的记载“基本有序”时，再对合座记载进行挨次平直插入排序
1. 算法门径 1）采用一个增量序列 t1，t2，……，tk，其中 ti > tj， tk = 12）按增量序列个数 k，对序列进行 k 次排序3）每次排序，凭证对应的增量 ti，将待排序列分割成多少长度为 m 的子序列，分别对各子表进行平直插入排序。仅增量因子为 1 时，通盘序列作为一个表来管制，表长度即为通盘序列的长度这是博主网上找的图片，更便捷贯通递减增量排序的经由
图片
2. 代码void BSortMethod::shellSort(int *vec， int len)
{
// 运转增量 gap = len / 2，逐步舒缓增量 gap = gap / 2 直到变为 1
for ( int gap = len / 2; gap >=1; gap = gap / 2 )
{
// 每一组进行排序
for ( int i = gap; i < len; ++i )
{
int temp = vec[i];
int j = i - gap;
while ( j >= 0 && vec[j] > temp )
{
vec[j+gap] = vec[j];
j -= gap;
}
vec[j+gap] = temp;
}
}
}
图片
五. 归并列序
归并列序（Merge Sort）是成立在归并操作上的一种有用的排序算法。该算法是采选分治法（Divide and Conquer）的一个相当典型的应用，作为一种典型的分而治之想想的算法应用，归并列序的杀青由两种门径：
从上至下的递归（总计递归的门径都不错用迭代重写，是以就有了第 2 种门径）；从下到上的迭代；和采用排序一样，归并列序的性能不受输入数据的影响，但发扬比采用排序好的多，因为恒久都是 O(nlogn) 的时分复杂度。代价是需要至极的内存空间
1. 算法门径 1）央求空间，使其大小为两个一经排序序列之和，该空间用来存放合并后的序列2）设定两个指针，当先位置分别为两个一经排序序列的肇端位置3）相比两个指针所指向的元素，采用相对小的元素放入到合并空间，并移动指针到下一位置4）重迭门径 3 直到某一指针达到序列尾5）将另一序列剩下的总计元素平直复制到合并序列尾 2. 代码void BSortMethod::merge(int *vec， int len)
{
int mid = len / 2; // mid将数组从中间分割
int *arr = new int[len]; // 临时数组（至极的内存空间）
int s = 0; // 临时数组的肇端位置
int first = 0， second = mid; // 两个数组的肇端位置
while ( first < mid && second < len )
{
// 相比大小
if ( vec[first] <= vec[second] ) {
arr[s++] = vec[first++];
} else {
arr[s++] = vec[second++];
}
}
// 将剩余项复制到临时数组中
while ( first < mid )
{
arr[s++] = vec[first++];
}
while ( second < len )
{
arr[s++] = vec[second++];
}
// 临时数组复制到原数组
for (int i = 0; i < len; ++i)
{
vec[i] = arr[i];
}
// 内存开释
delete []arr;
}
void BSortMethod::mergeSort(int *vec， int len)
{
// 递归出口
if ( len < 2 ) {
return;
}
mergeSort(vec， len / 2); // 对前半部分进行归并列序
mergeSort(vec + len / 2， len - len / 2); // 对后半部分进行归并列序
merge(vec， len); // 归并两部分
}
图片
3. 服从展示
图片
六. 快速排序快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法。速排序又是一种分而治之想想在排序算法上的典型应用。它的基本想想是通过一组排序将要排序的数据分割成稳定的两部分，其中一部分的所稀有据都比另外一部分的所稀有据小，然后再按此门径对这两部分数据进行快速排序，通盘排序过程不错递归进行，以此使所稀有据形成有序序列
1. 算法门径 1）从数列中挑出一个元素，称为 “基准”2）从新排序数列，总计元素比基准值小的摆放在基准前边，总计元素比基准值大的摆在基准的背面（相通的数不错到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形，是数列的大小是零或一，也等于长期都一经被排序好了。天然一直递归下去，然则这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它临了的位置去 2. 代码void BSortMethod::swap(int *vec， int i， int j)
{
int temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
int BSortMethod::partition(int *vec， int left， int right)
{
int pivot = left;
int index = pivot + 1;
int i = index;
while ( i <= right )
{
if ( vec[i] < vec[pivot] ) {
swap(vec， i， index);
index += 1;
}
i += 1;
}
swap(vec， pivot， index - 1);
// 复返最终辞别完成后基准元素场合的位置
return index - 1;
}
void BSortMethod::quickSort(int *vec， int left， int right)
{
if ( left < right ) {
int mid = partition(vec， left， right);
quickSort(vec， left， mid - 1);
quickSort(vec， mid + 1， right);
}
}
图片
3. 服从展示
图片
七. 堆排序堆排序（Heap Sort）是指欺骗堆这种数据结构所假想的一种排序算法。堆积是一个类似王人备二叉树的结构，并同期舒服堆积的性质：即子结点的键值或索引老是小于（或者大于）它的父节点。堆排序不错说是一种欺骗堆的主见来排序的采用排序。分为两种门径：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法顶用于升序胪列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法顶用于降序胪列；堆排序的平均时分复杂度为 Ο(nlogn)
1. 算法门径 1）创建一个堆 H[0……n-1]2）把堆首（最大值）和堆尾互换3）把堆的尺寸舒缓 1，并调用 shift_down(0)，指标是把新的数组尖端数据颐养到相应位置4）重迭门径 2，直到堆的尺寸为 1 2. 代码void BSortMethod::heapify(int *vec， int i， int len)
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if ( left < len && vec[left] > vec[largest] ) {
largest = left;
}
if ( right < len && vec[right] > vec[largest] ) {
largest = right;
}
if ( largest != i ) {
swap(vec， i， largest);
heapify(vec， largest， len);
}
}
void BSortMethod::heapSort(int *vec， int len)
{
// 从临了一个非叶子节点动手朝上遍历，创建堆
for ( int i = len / 2 - 1; i >= 0; i-- )
{
heapify(vec， i， len);
}
for ( int j = len - 1; j > 0; j-- )
{
swap(vec， 0， j);
heapify(vec， 0， j);
}
}
3. 服从展示
图片
八. 计数排序计数排序（Counting Sort）的中枢在于将输入的数据值滚动为键存储在至极征战的数组空间中。作为一种线性时分复杂度的排序，计数排序条件输入的数据必须是有细目范围的整数
1. 算法门径 1）找出待排序的数组中最大元素2）统计数组中每个值为 i 的元素出现的次数，存入计数数组C的第 i-1 项3）遍历计数数组C，将统计好的元素取出来放回原始数组 2. 代码void BSortMethod::countingSort(int *vec， int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 凭证找到的最大值来细目统计数组的长度
int arrayLen = max + 1;
// 动态央求内存，并运滚动为 0
int *array = new int[arrayLen] {0};
// 遍历数组，填充统计数组（把原数组中的数据变为统计数组的索引，值都是1）
for ( int j = 0; j < len; ++j )
{
array[vec[j]]++;
}
int index = 0;
for ( int k = 0; k < arrayLen; ++k )
{
// 遍历统计数组，再把排序后的索引变回数值存在底本数组中
while ( array[k] > 0 )
{
vec[index++] = k;
array[k]--;
}
}
// 开释内存
delete []array;
}
3. 服从展示
图片
九. 桶排序桶排序（Bucket Sort）是计数排序的升级版。它欺骗了函数的映射关连，高效与否的重要就在于这个映射函数的细目。为了使桶排序愈加高效，咱们需要作念到这两点：在至极空间饱和的情况下，尽量增大桶的数目使用的映射函数好像将输入的 N 个数据均匀的分拨到 K 个桶中同期，关于桶中元素的排序，采用何种相比排序算法关于性能的影响至关紧要
什么技巧最快：当输入的数据不错均匀的分拨到每一个桶中什么技巧最慢：当输入的数据被分拨到了归并个桶中 1. 算法门径 1）成立一个定量的数组看成空桶2）遍历序列，并将元素一个个放到对应的桶中3）对每个不是空的桶进行排序4）从不是空的桶里把元素再放回底本的序列中 2. 代码// 门径一
void BSortMethod::bucketSort(int *vec， int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 成立10个桶
const int bucketNum = 10;
// 界说二维数组
std::vector<int> buckets[bucketNum];
// 诡计桶的最大尺寸
int bucketSize = 1;
while (max) {
max /= 10;
bucketSize *= 10;
}
bucketSize /= 10;
// 数据存入桶中
for ( int i = 0; i < len; ++i )
{
// 界说元素存放的桶号
int index = vec[i] / bucketSize;
buckets[index].push_back(vec[i]);
// 对该桶使用插入排序
for ( int j = int(buckets[index].size()) - 1; j > 0; --j )
{
if ( buckets[index][j] < buckets[index][j-1] ) {
int temp = buckets[index][j];
buckets[index][j] = buckets[index][j-1];
buckets[index][j-1] = temp;
}
}
}
// 规定造访桶，取得有序数组
for ( int i = 0， k = 0; i < bucketNum; ++i )
{
for ( int j = 0; j < int(buckets[i].size()); ++j )
{
vec[k++] = buckets[i][j];
}
}
}
// 门径二
void BSortMethod::bucketSort2(int *vec， int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值，最小值
int min = vec[0];
int max = vec[0];
for ( int i = 1; i < len; ++i)
{
if ( vec[i] < min ) min = vec[i];
if ( vec[i] > max ) max = vec[i];
}
// 桶的大小
int bucketNum = (max - min) / len + 1;
// 二维数组动态分拨内存
int **buckets = new int* [bucketNum];
for ( int i = 0; i < bucketNum; ++i )
{
buckets[i] = new int[bucketNum] {0};
}
// 动态分拨内存，存储每个桶的元素个数
int *array = new int[bucketNum] {0};
// 数据存入桶中
for ( int i = 0; i < len; ++i )
{
// 界说元素存放的桶号
int index = (vec[i] - min) / len;
// 参考计数排序，填充统计数组
buckets[index][array[index]++] = vec[i];
}
int index = 0;
for ( int i = 0; i < bucketNum; ++i )
{
// 使用快速排序
quickSort(buckets[i]， 0， array[i] - 1);
cout << i << "号桶的元素个数：" << array[i] << endl;
// 遍历桶中元素，挨次存入原数组
for ( int j = 0; j < array[i]; ++j )
{
vec[index++] = buckets[i][j];
}
}
// 开释内存
delete[] buckets;
delete[] array;
}
十. 基数排序
基数排序（Radix Sort）是一种非相比型整数排序算法，其旨趣是将整数按位数切割成不同的数字，然后按每个位数分别相比。由于整数也不错抒发字符串（比如名字或日历）和特定状貌的浮点数，是以基数排序也不是只可使用于整数
1. 基数排序 vs 计数排序 vs 桶排序这三种排序算法都欺骗了桶的主见，但对桶的使用门径上有彰着各异：
计数排序：每个桶只存储单一键值；桶排序：每个桶存储一定范围的数值；基数排序：凭证键值的每位数字来分拨桶； 2. 代码void BSortMethod::radixSort(int *vec， int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 诡计最大值的位数
int maxBit = 1;
while ( max > 10 * maxBit )
{
maxBit++;
}
for ( int k = 0; k < maxBit; ++k )
{
// 界说桶（二维数组）
std::vector<std::vector<int>> bucket;
for ( int i = 0; i < 10; ++i )
{
std::vector<int> temp;
bucket.push_back(temp);
}
// 对每一位进行排序
for ( int i = 0; i < len; ++i )
{
// 取得每位的基数
int radix = int((vec[i] / (int)pow(10， k)) % 10);
// 将对应的数组元素添加到相应位基数的桶中
bucket[radix].push_back(vec[i]);
}
int index = 0;
for ( int i = 0; i < 10; ++i )
{
// 诡计桶的元素个数
int size = (int)bucket[i].size();
if ( size != 0 ) {
// 桶不为空时，将桶中每个元素放回到数组中
for ( int j = 0; j < size; ++j )
{
vec[index++] = bucket[i][j];
}
}
}
}
}
图片
3. 放浪展示
图片
函数调用#include "bsortmethod.h"
#include "iostream"
using namespace std;
int main()
{
int vec[15] = {3， 44， 38， 5， 47， 15， 36， 26， 27， 2， 46， 4， 19， 50， 48};
int len = sizeof(vec) / sizeof(*vec);
BSortMethod sortM;
// sortM.bubbleSort(vec， len); // 冒泡排序
// sortM.selectionSort(vec， len); // 采用排序
// sortM.insertionSort(vec， len); // 插入排序
// sortM.shellSort(vec， len); // 希尔排序
// sortM.mergeSort(vec， len); // 归并列序
// sortM.quickSort(vec， 0， len-1); // 快速排序
// sortM.heapSort(vec， len); // 堆排序
// sortM.countingSort(vec， len); // 计数排序
// sortM.bucketSort(vec， len); // 桶排序1
// sortM.bucketSort2(vec， len); // 桶排序2
sortM.radixSort(vec， len); // 基数排序
for(int i = 0; i < 15; ++i)
cout << vec[i] << " ";
cout << endl;
}
Github 代码
源代码下载空姐 偷拍
本站仅提供存储做事，总计施行均由用户发布，如发现存害或侵权施行，请点击举报。