八大排序
原创
:sun_with_face: 八大排序算法
:sun_with_face: 关系和复杂度
:sun_with_face: 关系
:sun_with_face: 复杂度
:sun_with_face: 一、冒泡排序
:sun_with_face: 原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
:sun_with_face: 代码
#include <stdio.h>
void bubble_sort(int a[], int size);
int main()
{
int a[7] = {1, 2, 4, 5, 3, 9, 8};
bubble_sort(a, 7);
for (int i = 0; i < 7; ++i)
{
printf("%d ", a[i]);
}
return 0;
}
void bubble_sort(int a[], int size)
{
for (int i = 0; i < size - 1; ++i)
{
for (int j = 0; j < size - 1 - i; ++j)
{
if (a[j] > a[j + 1])
{
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
}:sun_with_face: 二、选择排序
:sun_with_face: 原理
选择排序与冒泡排序有点像，只不过选择排序每次都是在确定了最小数的下标之后再进行交换，大大减少了交换的次数
:sun_with_face: 代码
#include <stdio.h>
void select_sort(int a[], int size);
int main()
{
int a[7] = {10, 2, 4, 5, 3, 9, 8};
select_sort(a, 7);
for (int i = 0; i < 7; ++i)
{
printf("%d ", a[i]);
}
return 0;
}
void select_sort(int a[], int size)
{
for (int i = 0; i < size - 1; ++i)
{
int minIndex = i;
for (int j = i; j < size; ++j)
{
if (a[j] < a[minIndex])
minIndex = j;
}
if (minIndex != i)
{
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}:sun_with_face: 三、插入排序
:sun_with_face: 原理
将一个记录插入到已排序的有序表中，从而得到一个新的，记录数增1的有序表
:sun_with_face: 代码
#include <stdio.h>
void insert_sort(int a[], int size);
int main()
{
int a[7] = {8, 2, 4, 5, 3, 9, 10};
insert_sort(a, 7);
for (int i = 0; i < 7; ++i)
{
printf("%d ", a[i]);
}
return 0;
}
void insert_sort(int a[], int size)
{
for (int i = 1; i < size - 1; ++i)
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}:sun_with_face: 四、快速排序
:sun_with_face: 原理
通过一趟排序将序列分成左右两部分，其中左半部分的的值均比右半部分的值小，
然后再分别对左右部分的记录进行排序，直到整个序列有序。
:sun_with_face: 代码
#include <iostream>
#include <vector>
using namespace std;
int division(vector<int> &list, int left, int right);
void quick_sort(vector<int> &list, int left, int right);
int main()
{
int arr[] = {8, 2, 4, 5, 3, 9, 10};
vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
cout << "排序前" << endl;
for (int i = 0; i < test.size(); i++)
{
cout << test[i] << " ";
}
cout << endl;
vector<int> result = test;
quick_sort(result, 0, result.size() - 1);
cout << "排序后" << endl;
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
int division(vector<int> &list, int left, int right)
{
// 以最左边的数(left)为基准
int base = list[left];
while (left < right)
{
// 从序列右端开始，向左遍历，直到找到小于base的数
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，将这个元素放到最左边的位置
list[left] = list[right];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，将这个元素放到最右边的位置
list[right] = list[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大。
list[left] = base;
return left;
}
// 快速排序
void quick_sort(vector<int> &list, int left, int right)
{
// 左下标一定小于右下标，否则就越界了
if (left < right)
{
// 对数组进行分割，取出下次分割的基准标号
int base = division(list, left, right);
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quick_sort(list, left, base - 1);
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quick_sort(list, base + 1, right);
}
}:sun_with_face: 五、堆排序
:sun_with_face: 原理
假设序列有n个元素,先将这n建成大顶堆，然后取堆顶元素，与序列第n个元素交换，然后调整前n-1元素，使其重新成为堆，然后再取堆顶元素，与第n-1个元素交换，再调整前n-2个元素...直至整个序列有序。
堆是一棵顺序存储的完全二叉树。
:sun_with_face: 代码
#include <iostream>
#include <vector>
using namespace std;
void heap_adjust(vector<int> &list, int parent, int length);
vector<int> heap_sort(vector<int> list);
int main()
{
int arr[] = {6, 4, 8, 9, 2, 3, 1};
vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
cout << "排序前:";
for (int i = 0; i < test.size(); i++)
{
cout << test[i] << " ";
}
cout << endl;
vector<int> result;
result = heap_sort(test);
cout << "排序后:";
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
void heap_adjust(vector<int> &list, int parent, int length)
{
int temp = list[parent]; // temp保存当前父节点
int child = 2 * parent + 1; // 先获得左孩子
while (child < length)
{
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (child + 1 < length && list[child] < list[child + 1])
{
child++;
}
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (temp >= list[child])
{
break;
}
// 把孩子结点的值赋给父结点
list[parent] = list[child];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = child;
child = 2 * parent + 1;
}
list[parent] = temp;
}
vector<int> heap_sort(vector<int> list)
{
int length = list.size();
// 循环建立初始堆
for (int i = length / 2 - 1; i >= 0; i--)
{
heap_adjust(list, i, length);
}
// 进行n-1次循环，完成排序
for (int i = length - 1; i > 0; i--)
{
// 最后一个元素和第一元素进行交换
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 筛选 R[0] 结点，得到i-1个结点的堆
heap_adjust(list, 0, i);
cout << "第" << length - i << "趟排序:";
for (int i = 0; i < list.size(); i++)
{
cout << list[i] << " ";
}
cout << endl;
}
return list;
}:sun_with_face: 六、希尔排序
:sun_with_face: 原理
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
:sun_with_face: 代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> shell_sort(vector<int> list);
int main()
{
int arr[] = {6, 4, 8, 9, 2, 3, 1};
vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
cout << "排序前" << endl;
for (int i = 0; i < test.size(); i++)
{
cout << test[i] << " ";
}
cout << endl;
vector<int> result;
result = shell_sort(test);
cout << "排序后" << endl;
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
vector<int> shell_sort(vector<int> list)
{
vector<int> result = list;
int n = result.size();
for (int gap = n >> 1; gap > 0; gap >>= 1)
{
for (int i = gap; i < n; i++)
{
int temp = result[i];
int j = i - gap;
while (j >= 0 && result[j] > temp)
{
result[j + gap] = result[j];
j -= gap;
}
result[j + gap] = temp;
}
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
}
return result;
}:sun_with_face: 七、归并排序
:sun_with_face: 原理
- 把有序表划分成元素个数尽量相等的两半
- 把两半元素分别排序
- 把两个有序表合并成一个
:sun_with_face: 代码
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int> &input, int left, int mid, int right, vector<int> temp);
void MergeSort(vector<int> &input, int left, int right, vector<int> temp);
void merge_sort(vector<int> &input);
int main()
{
int arr[] = {6, 4, 8, 9, 2, 3, 1};
vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
cout << "排序前:";
for (int i = 0; i < test.size(); i++)
{
cout << test[i] << " ";
}
cout << endl;
vector<int> result = test;
merge_sort(result);
cout << "排序后:";
for (int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
void merge(vector<int> &input, int left, int mid, int right, vector<int> temp)
{
int i = left; // i是第一段序列的下标
int j = mid + 1; // j是第二段序列的下标
int k = 0; // k是临时存放合并序列的下标
// 扫描第一段和第二段序列，直到有一个扫描结束
while (i <= mid && j <= right)
{
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if (input[i] <= input[j])
{
temp[k++] = input[i++];
}
else
{
temp[k++] = input[j++];
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while (i <= mid)
{
temp[k++] = input[i++];
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while (j <= right)
{
temp[k++] = input[j++];
}
k = 0;
// 将合并序列复制到原始序列中
while (left <= right)
{
input[left++] = temp[k++];
}
}
void MergeSort(vector<int> &input, int left, int right, vector<int> temp)
{
if (left < right)
{
int mid = (right + left) >> 1;
MergeSort(input, left, mid, temp);
MergeSort(input, mid + 1, right, temp);
merge(input, left, mid, right, temp);
}
}
void merge_sort(vector<int> &input)
{
// 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
vector<int> temp(input.size());
MergeSort(input, 0, input.size() - 1, temp);
}:sun_with_face: 八、计数排序
:sun_with_face: 原理
当待排序的数的值都是在一定的范围内的整数时，可以用待排序的数作为计数数组的下标，统计每个数的个数，然后依次输出即可。
:sun_with_face: 代码
#include <stdio.h>
void count_sort(int a[], int size);
int main()
{
int a[7] = {10, 2, 4, 5, 3, 9, 8};
count_sort(a, 7);
for (int i = 0; i < 7; ++i)
{
printf("%d ", a[i]);
}
return 0;
}
void count_sort(int a[], int size)
{
int mx = a[0];
for (int i = 1; i < size; ++i)
mx = a[i] > mx ? a[i] : mx;
int *count = new int[mx + 1](); //有() 默认初值为0
for (int i = 0; i < size; ++i)
count[a[i]]++;
int id = 0;
for (int i = 0; i <= mx; ++i)
{
for (int j = 0; j < count[i]; ++j)
a[id++] = i;
}
delete[] count;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
