|
目录
稳定性：
一、冒泡排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
二、选择排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
三、插入排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
四、希尔排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
五、归并排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
六、快速排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
七、基数排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
八、堆排序
? ? ? ? 概念：
? ? ? ? 特点：
? ? ? ? 复杂度：
? ? ? ? 代码演示：
稳定性：
????????在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称该排序算法是稳定的。
????????例如：数组a? =? {1,?2, 3, 4, 1}，经过排序后为{1, 1, 2, 3, 4}。若第一个1为原先下标为0，第二个1为原先下标为4，则该排序算法是稳定的；若第一个1为原先下标为4，第二个1为原先下标为0，则该排序算法是不稳定的。
? ? ? ? 稳定性的排序算法有：冒泡排序，插入排序、归并排序、基数排序。
? ? ? ? 不稳定的排序算法有：选择排序、希尔排序、快速排序、堆排序。
以下排序默认为从小到大排序
一、冒泡排序
? ? ? ? 概念：
? ? ? ? 冒泡排序通过不断比较两个相邻的元素，若前一个元素较大则交换，重复（n-i-1）次为1轮（i表示第i轮，从0开始），重复（n-1）轮后排序完成（最后一轮只有一个元素，所以不用比较）。较小的元素会经由交换慢慢“浮”到数列的前端。
? ? ? ? 特点：
? ? ? ? ①冒泡排序是稳定的排序方法②每次比较只比较相邻的两个元素。③每交换一轮就会将一个最大的元素置于数组的最后，即每经过一轮比较，需要比较的元素减一。通俗点说就是每进行一轮就会将当前数组中最大的元素放最后，之后要比较的数组元素减一。
? ? ? ? 复杂度：
????????时间复杂度O（N2）。空间复杂度O（1）。
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void bubble_sort(int a[], int n) { //传入数组，数组长度
for (int i = 0; i < (n-1); i++) { //总共会进行n轮
for (int j = 0; j < (n - i - 1); j++) { //一轮会比较n-i-1次(还要减去1防止越界）
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
int main()
{
int a[] = { 2, 5, 6, 8, 2, 4, 3 };
for (int i : a) { cout << i << " "; }
cout << endl;
bubble_sort(a, sizeof(a) / sizeof(a[0]));
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
二、选择排序
? ? ? ? 概念：
? ? ? ? 找出数组中未排序部分的最小值下标，然后将其与未排序部分的首元素交换，重复n-1次即可。
? ? ? ? 特点：
? ? ? ? ①选择排序是不稳定排序。②每排序一次都会将未排序数组的最小值放到最前，即每次排序后，最前面的是元素都比后面小。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度O（n2），空间复杂度O（1）。
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void selection_sort(int a[], int n) {
for (int i = 0; i < (n - 1); i++) { //总共查找n-1次最小值
int t = i; //当前的最小值下标
for (int j = i + 1; j < n; j++) { //寻找未排序部分的最小值下标。
if (a[j] < a[t]) {
t = j;
}
}
if (t != i) { //如果第a[i]不是当前最小的
int temp = a[i];
a[i] = a[t];
a[t] = temp;
}
}
}
int main()
{
int a[] = { 5, 2, 4, 6, 8, 6, 4 };
for (int i : a) { cout << i << " "; }
cout << endl;
selection_sort(a, sizeof(a) / sizeof(a[0]));
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
三、插入排序
? ? ? ? 概念：
????????将一个元素插入到已经排好序的有序表中，从而得到一个新的、元素数增1的有序表。
? ? ? ? 特点：
? ? ? ? ①插入排序是稳定的②进行 k次排序后前k+1个元素是有序的。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度O（n2）， 空间复杂度O（1）。
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void snsertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) { //默认第一个元素a[0]是排好序的，所以从1开始
int t = i; //待插入元素的位置
for (int j = i - 1; j >= 0; j--) { //注意是从后往前比较，所以是j--
if (a[t] < a[j]) {
int temp = a[t];
a[t] = a[j];
a[j] = temp;
t = j; //注意哦，下标也要变化
}
else {
break;
}
}
}
}
int main()
{
int a[] = { 5, 2, 4, 6, 8, 6, 4 };
for (int i : a) { cout << i << " "; }
cout << endl;
snsertion_sort(a, sizeof(a) / sizeof(a[0]));
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
四、希尔排序
? ? ? ? 概念：
? ? ? ? 希尔排序基于插入排序改进，先取一个小于n的整数d1作为第一个增量（一般是n/2），把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行插入排序，然后，取第二个增量d2（一般取d1的一半），重复以上步骤直到增量为1进行最后一次插入排序。
? ? ? ? 特点：
? ? ? ? ①希尔排序是不稳定的②每次排序都会将增量为d的元素排好序。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度为O（nlog2n），空间复杂度为O（1）。
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void shells_sort(int a[], int n) {
int d = n / 2;
while (d) { //当d不为0时进行排序
for (int i = 0; i < d; i++) { //分成d组
for (int j = i + d; j < n; j += d) { //对每一组进行插入排序
int t = j;
for (int k = j - d; j >= i; j -= d) {
if (a[t] < a[k]) {
int temp = a[t];
a[t] = a[k];
a[k] = temp;
t = k;
}
else {
break;
}
}
}
}
d /= 2;
}
}
int main()
{
int a[] = { 5, 2, 4, 6, 8, 6, 4 };
for (int i : a) { cout << i << " "; }
cout << endl;
shells_sort(a, sizeof(a) / sizeof(a[0]));
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
五、归并排序
? ? ? ? 概念：
? ? ? ?先将数组不断二分出子数组直到每个子数组的元素数目均为1，此时每个子数组都是有序的，然后两两合并有序的子数组，重复该合并步骤。（合并方式为：比较两个子数组的首个元素，将小的放进新的空间中，然后重复这一步骤）
? ? ? ? 特点：
? ? ? ? ①归并排序是稳定的②每一次合并都会合并2的倍数个有序元素。即第i次合并后每2的i次方个元素是有序的。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度O（nlogn），空间复杂度O（n）
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void merge(int a[], int left, int middle, int right) {
int* b = new int[right - left + 1]; //创建一个数组b用来接收有序数组
int i = left, j = middle + 1;
int k = 0;
for (; (i <= middle) && (j <= right); ) { //将小的元素按序存入直到一个子数组全存入
if (a[i] <= a[j]) { //这里要用小于等于，不然可能会变成不稳定的排序
b[k++] = a[i++];
}
else {
b[k++] = a[j++];
}
}
if (i > middle) { //将剩余的也按序存入
for (; j <= right; j++) { b[k++] = a[j]; }
}
else {
for (; i <= middle; i++) { b[k++] = a[i]; }
}
for (int i = left; i <= right; i++) { a[i] = b[i-left]; } //赋值回数组a
delete[]b; //new完先delete
}
void merge_sort(int a[], int left, int right) { //归并排序,参数为数组，数组下标的最小值和最大值。
if (right <= left) { return; } //当子数组长度为1时停止二分。
int middle = (left + right) / 2;
//先将数组不断二分
merge_sort(a, left, middle);
merge_sort(a, middle+1, right);
//合并二分后的有序数组。
merge(a, left, middle, right);
}
int main()
{
int a[] = { 5, 2, 4, 6, 8, 6, 4 };
for (int i : a) { cout << i << " "; }
cout << endl;
merge_sort(a, 0, sizeof(a) / sizeof(a[0])-1); //注意，是下标值，所以要减一
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
六、快速排序
? ? ? ? 概念：
? ? ? ? 先设置一个分界值（通常是第一个元素），将数组分为小于分界值和大于分界值两部分，重复这一步骤。
? ? ? ? 特点：
? ? ? ? ①快速排序是一个不稳定排序②每排序一次，分界值左边的值都小于分界值，右边的值都大于分界值。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度为O（nlog2n），空间复杂度为O（log2n）
? ? ? ? 代码演示：
#include <iostream>
using namespace std;
void swap(int a[], int l, int r) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
void quick_sort(int a[], int left, int right) {
if (left >= right) { return; }
int l = left, r = right, t = left;
while (l < r) {
while (a[r] >= a[t]) { r--; }
if (r > l) { swap(a, t, r); t = r; }
else { break; }
while (a[l] <= a[t]) { l++; }
if (l < r) { swap(a, t, l); t = l; }
}
quick_sort(a, left, t - 1);
quick_sort(a, t+1, right);
}
int main()
{
int a[] = { 5, 2, 4, 6, 8, 6, 4 };
for (int i : a) { cout << i << " "; }
cout << endl;
quick_sort(a, 0, sizeof(a) / sizeof(a[0])-1); //注意，是下标值，所以要减一
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
七、基数排序
? ? ? ? 概念：
? ? ? ? 先创建一个10个桶（编号从0到9）（可以是二维的动态数组），然后将数组中的元素按个位数的大小放入对应的桶中（这算第零轮）。找出数组中最大的位数k，重复以下操作k-1次：按顺序取出桶中元素（先取出编号为0的桶的所有元素，再取出为1的...），找出他们在该位数的数（第一轮就是十位数，第二轮就是百位数...）放入对应的新桶中（也是编号从0到9的10个桶）。重复完成后再遍历所有的桶，将值按序赋给数组。
? ? ? ? 特点：
? ? ? ? ①基数排序是稳定的②每一轮的桶中都是按基数进行排序的。
? ? ? ? 复杂度：
????????时间复杂度O (nlog(r)m)，其中r为所采取的基数（桶的数量），而m为堆数（最大值的位数），空间复杂度O（n+m），m为桶的数量。
? ? ? ? 代码演示：
#include <iostream>
#include<vector>
using namespace std;
int maxbit(int a[], int n) {
int t = a[0], bit = 0; //最大值与其位数
for (int i = 1; i < n; i++) { //找出最大值
if (a[i] > t) { t = a[i]; }
}
while (t) { //求位数
bit++;
t /= 10;
}
return bit;
}
void radix_sort(int a[], int n) {
vector<vector<int> > v(10); //其实用链表存更好，但我懒。注意，这里第一行全是0.
for (int i = 0; i < n; i++) { //先进行一轮，之后就不用对a操作了
int yu = a[i] % 10;
v[yu].emplace_back(a[i]);
}
int k = maxbit(a, n); //先找出所有元素中最大值的位数
for (int i = 1; i < k; i++) { //一共进行k轮（由于先进行了一轮，所以从1开始）
vector<vector<int> > v1(10);
for (int i1 = 0; i1 < v[0].size(); i1++) { v1[0].emplace_back(v[0][i]); }
for (int j = 1; j < 10; j++) { //对数组v遍历,不用对v【0】的数操作。
int m = v[j].size();
for (int u = 0; u < m; u++) {
int t = (v[j][u] / (i * 10)) % 10; //求余数
v1[t].emplace_back(v[j][u]);
}
}
v = v1;
}
int tm = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < v[i].size(); j++) {
a[tm++] = v[i][j];
}
}
}
int main()
{
int a[] = { 5, 2, 24, 16, 8, 6, 4, 54};
for (int i : a) { cout << i << " "; }
cout << endl;
radix_sort(a, sizeof(a) / sizeof(a[0])); //注意，是下标值，所以要减一
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
八、堆排序
? ? ? ? 概念：
? ? ? ? 利用堆的性质所设计的（大根（顶）堆：父节点的值大于子节点的值）。将待排序的数组构造成一个大根堆，将顶端的数与末尾的数交换，此时末尾的数为最大值，再将剩下的数重复以上步骤。（第i个节点的子节点是2i+1和2i+2）。
? ? ? ? 特点：
? ? ? ? ①堆排序是不稳定的②没进行一次堆排序后，最大值会被换到最后，且除了a[0]和a[n-1]外，a[i] > max(a[2*i+1], a[2*i+2])。
? ? ? ? 复杂度：
? ? ? ? 时间复杂度O（nlogn），空间复杂度O（1）
? ? ? ? 代码演示：
#include <iostream>
#include<vector>
using namespace std;
void swap(int a[], int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void maxhead_sort(int a[], int n) { //升序，所以是大根（顶）堆
if (n <= 1) { return; }
for (int i = (n - 2) / 2; i >= 0; i--) { //最后一个节点下标是（n-2）/2。
int t = 2 * i + 1;
if (t < n - 1) {
if (a[2 * i + 1] < a[2 * i + 2]) { t += 1; }
}
if (a[t] > a[i]) { swap(a, i, t); }
}
swap(a, 0, n - 1); //将最大的数移到最后
maxhead_sort(a, n - 1); //剩余的数继续
}
int main()
{
int a[] = { 5, 2, 24, 16, 8, 6, 4, 54 };
for (int i : a) { cout << i << " "; }
cout << endl;
maxhead_sort(a, sizeof(a) / sizeof(a[0])); //注意，是下标值，所以要减一
for (int i : a) { cout << i << " "; }
cout << endl;
return 0;
}
|