插入排序
插入排序的前提是未插入时该序列有序。
假如是从小到大排序，插入的数为key，从右向左找小于等于key的值，如果不满足那么原来的向后移动一位进行覆盖，直到满足或者找完进行插入。
重复上面的操作。
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n-1; i++)
{
int end=i;
int key = a[end + 1];
while (end>=0)
{
if (a[end] <= key)
break;
else
a[end + 1] = a[end];
end--;
}
a[end + 1] = key;
}
}时间复杂度O(n*n)
该排序适合接近有序的情况下，在该种情况下时间复杂度接近O(n)
希尔排序
有插入排序演变过来
希尔排序有两个步骤：
1.预排序（尽可能变得有序）
2.插入排序
例：
预排序：把待排序的一组数分为gap组，每一组进行插入排序
把这10组数分成3组：
第1组：2，5，3，0
第2组：4，1，8
第3组：6，9，7
经过预排之后的顺序
最后全部的进行插入排序，就可以得到有序的序列。
上面例子的代码：
void ShellSort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n-gap; i++)
{
int end=i;
int key = a[end + gap];
while (end >= 0)
{
if (a[end] <= key)
break;
else
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = key;
}
InsertSort(a, n);
}希尔排序动态图
void ShellSort(int* a, int n)
{
int gap = n;
while (gap>1)
{
gap = gap / 2;
for (int i = 0; i < n-gap; i++)
{
int end = i;
int key = a[end + gap];
while (end >= 0)
{
if (a[end] <= key)
break;
else
a[end + gap] = a[end];
end -= gap;
}
a[end + gap] = key;
}
}
}选择排序
选择排序很简单，每一次选出最小的反在前面，选出最大的放在后面。
void SelectSort(int* a, int n)
{
int min, max;
int begin = 0, end = n - 1;
while (begin < end)
{
min = max = begin;
for (int i = begin; i <= end; i++)
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
swap(&a[min], &a[begin]);
//注意
if (begin == max)
max = min;
swap(&a[max], &a[end]);
begin++;
end--;
}
}注意两两交换的情况：
如果这4个下标指向的各不相同时，两两交换没有任何问题。
唯一要注意的情况是begin==max的时候，必须修改max，因为此时max的值不是最大而是变成最小，需要修改max，注意不能修改end，begin，end为边界控制。end==min的这种情况不需要修改，因为max没有变，还是要跑到最后的。
时间复杂度O(N*N)
堆排序
void AdjustDwon(int* a, int n, int root)
{
int father = root;
int child = 2 * father + 1;
while (child <n)
{
if (child<n - 1 && a[child]<a[child + 1])
child++;
if (a[father] < a[child])
{
swap(&a[father], &a[child]);
father = child;
child = 2 * father + 1;
}
else
return;
}
}
void HeapSort(int* a, int n)
{
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
for (i = n - 1; i > 0; i--)
{
swap(&a[0], &a[i]);
AdjustDwon(a, i-1, 0);
}
}冒泡排序
void BubbleSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
for (int i = begin; i < n-1; i++)
{
for (int j = begin; j < end; j++)
{
if (a[j+1] < a[j])
swap(&a[j], &a[j+1]);
}
end--;
}
}以前的文章
目录
桶排序（简化版）
冒泡排序
1.桶排序（简化版）
所谓桶排序就是桶的序列是排好的，只需要把数字放在对应桶的序列就可以，记下这个桶里面数字出现过几次就可以。
我们来排个数吧！3 4 6 8 5 2 9 7 1
我们需要的桶数由最大数+1构成，所以占内存比较大，但时间复杂度小。用数组来储存，arr[10],数组的下标是从0开始的。先把桶都先初始化为0，表示没有一个数出现过.
先讲一下一维数组的初始化
这是一种初始化
int arr[10] = { 0 };这样虽然初始化第一个元素，都是下面的各个元素都被默认为0
还可以这样初始化，下面的这种开始声明的并没有初始化，后续是进行的赋值
int arr[10];
int n = 0;
for (n = 0; n < 10; n++)
{
arr[n] = 0;
}在平时的初始化中我喜欢第一种。
下面我们循环输入刚才的数 3 4 6 8 5 2 9 7 1
并且把数存到相应的桶中，并记录出现几次
for (n = 0; n < 9; n++)
{
scanf("%d", &s);
arr[s]++;
}接着我们把它输出就可以了（从小到大）
for (n = 0; n < 10; n++)
{
if (arr[n] != 0)
printf("%d ", n);
}完整代码
#include <stdio.h>
#define MAX 10
int main()
{
int arr[MAX]={0};
int n = 0,s=0;
for (n = 0; n < MAX-1; n++)
{
scanf("%d", &s);
arr[s]++;
}
for (n = 0; n < MAX; n++)
{
if (arr[n] != 0)
printf("%d ", n);
}
return 0;
}2.冒泡排序（基本思路前一个数与第二个数进行比较）
编辑
“冒泡”就像上面的图片一样，从下面到上面，我们这里讲的_冒泡排序 _就和这个类似
还是这样一个无序的数列** 3 4 6 8 5 2 9 7 1，我们想让它变成 1 2 3 4 5 6 7 8 9
假设有一个箭头J指向一个数
1）首先是J指向最下面的3， 它与J+1指向的数（也就是下一个数）进行比较，如果比它大，他俩就进行交换，否则不交换。然后J **往后走一步（j++），依此循环该步骤。直至到最后一个数的比较。这次找到的是最大的数。
for (j = 0; j < 9 - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}2）3 4 6 5 2 8 7 1 9 ，这是上一步排成的，可以观察到最后一个数已经排好了（可以理解为最大的气泡已经出水面了），下面的排序就是把已经排好的数字（每次排好的最后一个数）去掉，按照（1）进行排下列的数字.直至完成排序。
注意：
1.总排序此时为排序数字个数减1
2.每一次排序都减1
完整代码
int main()
{
int arr[9] = { 3 ,4, 6, 8, 5, 2, 9 ,7, 1 };
int i, j;
for (i = 0; i < 9 - 1; i++)
{
for (j = 0; j < 9 - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return 0;
}感兴趣的小伙伴可以对上面的冒泡排序的算法进行优化哦
快速排序
快速排序的基本思路就是：选出一个基值，一般是选取最左边的为基值，然后从右边开始进行遍历，假设是按从小到大的顺序，那么从右边找小的，找到小的之后，在从左边开始找最大的，找到之后两者进行交换。然后继续重复上面的过程，直到左边大于等于右边的时候停止，然后和基数进行交换。
这是一轮
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[keyi] <= a[right])
right--;
while (left < right && a[left] <= a[keyi])
left++;
swap(&a[left], &a[right]);
}
swap(&a[keyi], &a[right]);
keyi = left;
return keyi;
}坑位法：把基数作为坑位，从右边开始找小（比基数小）的，找到之后填入坑位，该位置变成坑位，然后从左边开始找大，然后再填入坑位，直到找完（左边大于等于右边），把基数填入坑位。
int PartSort2(int* a, int left, int right)
{
int keyi= left;
int temp = a[left];
while (left < right)
{
while (left<right&&a[right] >= temp)
{
right--;
}
a[keyi] = a[right];
keyi = right;
while (left < right && a[left] <= temp)
{
left++;
}
a[keyi] = a[left];
keyi = left;
}
a[keyi] = temp;
return keyi;
}前后指针法：
前指针从基数前一个位置开始，后指针从基数位置开始。前指针找小，当找到小的时候，后指针加一，然后前后指针指向的数值进行交换，然后前指针继续找小，直到查找完。
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int front = keyi + 1;
int back = keyi;
while (front <= right)
{
if (a[front] <= a[keyi])
{
back++;
swap(&a[front], &a[back]);
}
front++;
}
swap(&a[back], &a[keyi]);
keyi = back;
return keyi;
}上面描述的是一轮排序，每一轮排好之后，都可以确定好排好序之后基数的位置，基数左边是比它小的，右边是比它大的，左边继续排序，右边在继续排序。当还剩一个需要排序的时候就停止排序了。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
//keyi = PartSort1(a, left, right);
//keyi = PartSort2(a, left, right);
keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}上面这种排序还不可以，因为他的最坏的时间复杂度为O(N*N)，我们取的基数最好是该组有序数的中间值，但是这个值也不容易在无序中找到，此时我们用3数取中法，把最边的值，最右边的值，还有中间的值，3者进行比较，次大的为基数。为了保证还是上面的方法，我们把基数和最左边的数进行交换。
int ThreeIn(int* a, int left, int right)
{
int middle = left + (right - left) / 2;
if (a[middle] < a[left])
{
if (a[left] < a[right])
return left;
else if (a[middle] < a[right])
return right;
else
return middle;
}
else
{
if (a[middle] < a[right])
return middle;
else if (a[left] < a[right])
return right;
else
return left;
}
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int x = ThreeIn(a, left, right);
swap(&a[keyi], &a[x]);
//keyi = PartSort1(a, left, right);
//keyi = PartSort2(a, left, right);
keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}时间复杂度O(N*logN)
以最左边为基数，为什么从先右边开始呢？
在L与R交换的过程中没有什么可以讨论的，最主要的是相遇的时候和基数进行交换的情况：
1.R遇见L，此时L为最小的或者是基数，交换之后，左小右大。
2.L遇见R:
(1)L与R没有交换
R所处的位置为小，R右边都是大，左边都是小，可以与基值进行交换。
(2)L与R交换
交换过后R还是会继续移动到小的地方，然后和(1)一样。
我们再讨论选左边为基值，还是讨论相遇的情况
1.L遇见R
(1)没有发生交换就相遇了，无法判断相遇时与基值的大小。
(2)L与R交换过后再相遇，此时相遇的为大，不能和基值进行交换。
2.R遇见L
R遇见L说明R与L交换过，此时基值是小的，可以交换。
综上所述:从左边开始并不能完全保证相遇的地方为小的。
非递归形式的快速排序
1.用栈进行实现
用栈储存一组数的上下界，如果从左开始选基数的话，根据栈的特性，我们先储存左边界，再储存右边界。每次排序都从栈中拿出2个数据。当向栈中储存边界的时候要主要边界直接有没有元素。
void QuickSortNonR1(int* a, int left, int right)
{
Stack p;
InitStack(&p);
StackPush(&p, left);
StackPush(&p, right);
while (!StackEmpty(&p))
{
right = StackTop(&p);
StackPop(&p);
left = StackTop(&p);
StackPop(&p);
int keyi = PartSort3(a, left, right);
if (keyi + 1 < right)
{
StackPush(&p, keyi+1);
StackPush(&p, right);
}
if (keyi - 1 > left)
{
StackPush(&p, left);
StackPush(&p, keyi-1);
}
}
StackDestroy(&p);
}2.用队列实现
根据队列的性质，先储存右边界，再储存左边界。后面的过程和栈类似
void QuickSortNonR2(int* a, int left, int right)
{
Queue p;
QueueInit(&p);
QueuePush(&p, right);
QueuePush(&p, left);
while (!QueueEmpty(&p))
{
right = QueueFront(&p);
QueuePop(&p);
left= QueueFront(&p);
QueuePop(&p);
int keyi = PartSort3(a, left, right);
if (keyi - 1 > left)
{
QueuePush(&p, keyi - 1);
QueuePush(&p, left);
}
if (keyi + 1 < right)
{
QueuePush(&p, right);
QueuePush(&p, keyi + 1);
}
}
QueueDestroy(&p);
}归并排序
归并排序是先把待排序的集合无限划分，直到划分为有序的区间（其实就是只含一个数），对每个有序的区间进行归并，又得到了较大的有序区间，然后再归并，最后变成有序。这里在合并的时候需要开辟新的空间。
void merge_sort(int* a, int* temp, int left,int right)
{
//控制返回的条件
if (left >= right)
return;
int mid = left + (right - left) / 2;
//不断分割区间left,mid],[mid+1,right]
merge_sort(a, temp, left, mid);
merge_sort(a, temp, mid+1, right);
//归并
int L1 = left, R1 = mid;
int L2 = mid+1, R2 = right;
int i = L1;
//区间存在
while (L1 <= R1 && L2 <= R2)
{
if (a[L1] <= a[L2])
temp[i++] = a[L1++];
else
temp[i++] = a[L2++];
}
while (L1 <= R1)
temp[i++] = a[L1++];
while (L2 <= R2)
temp[i++] = a[L2++];
memcpy(a+left, temp+left, sizeof(int) * (right - left+1));
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
merge_sort(a, temp, 0,n-1);
free(temp);
}归并排序的非递归写法
从递归的里面可以发现，先是1个1个的归，然后是2个2个的归·········
在这个写法中，要注意边界的问题
void MergeSortNonR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
exit(-1);
int gap = 1;
//gap表示有几个几个有序，1为1个1个一组有序，2表示2个2个一组有序
while (gap < n)
{
int left1 = 0;
while (left1<n)
{
int right2 = left1 + 2*gap-1;
int mid = (left1 + right2) / 2;
int right1 = mid, left2 = mid + 1;
int i = left1; int x = left1;
if (right1 >= n)
{
right1 = n - 1;
left2 = n;
right2 = n-1;
}
else if (left2 >= n)
{
left2 = n;
right2 = n-1;
}
else if (right2 >= n)
{
right2 = n - 1;
}
while (left1 <= right1 && left2 <= right2)
{
if (a[left1] <= a[left2])
temp[i++] = a[left1++];
else
temp[i++] = a[left2++];
}
while (left1 <= right1)
temp[i++] = a[left1++];
while (left2 <= right2)
temp[i++] = a[left2++];
memcpy(a + x, temp + x, sizeof(int) * (right2 - x + 1));
left1 = right2 + 1;
}
gap *= 2;
}
free(temp);
}用归并排序的思想对存储在文件中的数据进行排序
基本步骤为：
- 把要排序的大文件分成若干小文件——这里我分成了10份
- 对每一个小文件进行排序——用快速排序快速完成，在内存级别拍好然后写好文件
- 对每2个小文件进行归并排序，并把归并排序好的写入第一个小文件
- 把第一个小文件和后面的小文件归并，把归并的结果继续放到第一个小文件
- 重复上述过程，直到拍好
- 最后把拍好的重新写回到原文件——这里我的源文件为
sort.txt
注意：注意文件的打开方式，换不同的打开方式的时候，注意关闭
#include <iostream>
#include <fstream>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
//生成随机数
fstream fsx("sort.txt");
srand((unsigned)time(nullptr));
for (int i = 0; i < 100; i++)
{
fsx << rand()%100 << endl;
}
fsx.close();
//fstream fsx("sort.txt", ios_base::out);
//for (int i = 0; i < 100; i++)
//{
// fsx << i << endl;
//}
//fsx.close();
//把文件分成10小份
int n = 10;//n表示小文件的个数
//同时对小文件用快速排序完成对小文件的排序
vector<string> filename(n, "sort");
fstream ifs("sort.txt", ios_base::in);
for (int i = 0; i < n; i++)
{
filename[i] += i + '0';
ofstream ofs(filename[i]);
int j = 0;
int number[10] = { 0 };
while (j < n)
{
ifs >> number[j++];
}
//排序
sort(number, number + n);
j = 0;
while (j < n)
{
ofs << number[j++] << endl;
}
}
ifs.close();
//对单个文件进行归并
fstream fs;
int a, b;
fstream readfile1;
fstream readfile2;
for (int i = 1; i < n; i++)
{
readfile1.open(filename[0], ios_base::in);
readfile2.open(filename[i], ios_base::in);
fs.open("mergesorttemp", ios_base::out);
readfile1 >> a;
readfile2 >> b;
while (readfile1.good() && readfile2.good())
{
if (a < b)
{
fs << a << endl;
readfile1 >> a;
}
else
{
fs << b << endl;
readfile2 >> b;
}
}
//把没有读完的数据进行读完
while (readfile1.good()) {
fs << a << endl;
readfile1 >> a;
}
while (readfile2.good()) {
fs << b << endl;
readfile2 >> b;
}
//readfile1.close();
//readfile1.open(filename[0]);
//把文件写会第一个文件
fs.close();
fs.open("mergesorttemp", ios_base::in);
readfile1.close();
readfile1.open(filename[0], ios_base::out);
while (fs.good()) {
fs >> a;
if (fs.good())
readfile1 << a << endl;;
}
readfile1.close();
readfile2.close();
fs.close();
}
readfile1.open(filename[0]);
ifs.open("sort.txt", ios_base::out);
while (readfile1.good()) {
readfile1 >> a;
if (readfile1.good())
ifs << a << endl;
}
return 0;
}计数排序
给定一组数，确定该组数的范围（最大与最小之间的范围），申请在这范围内的空间，统计每个数出现的次数。最后从新拷贝到原数据中
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0; i < n; i++)
{
if (min > a[i])
min = a[i];
if (max < a[i])
max = a[i];
}
int range = max - min+1;
int* temp = calloc(range, sizeof(int));
for (int i = 0; i < n; i++)
{
temp[a[i] - min]++;
}
for (int i = 0,j=0; i < range; i++)
{
while (temp[i]--)
a[j++] = i + min;
}
}基数排序
基数排序是一种非比较型整数排序算法，其原理是讲整数按照按位数切割成不同的数字，然后按每个数位分别比较。
下面是动态图。
从动态图中就可以看出，我们可以根据每位的大小，从小到大进行排序。
首先是个位，从0到9进行排。每一位上可能有多个数，这些数按照先进先出的方式进行排序。
下面实现一下：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/*
* 这里只是简单的实现一下，没有写的非常严格
*/
//x为需要提取位数的数据，k为要提取第几位数
//1为个位 2为十位
#define MAX_NUM 3 //最大有几位数
#define BASE_NUM 10 //基数
int GetDigit(int x,int k)
{
while (--k)
{
x /= 10;
}
return x % 10;
}
void print(int* p,int n)
{
for (int i = 0; i < n; i++) {
cout << p[i] << endl;
}
}
int main()
{
int arr[] = { 882,3,5,345,254,606,588,808,535,784,715,710 };
int n = sizeof(arr) / sizeof(arr[0]);
//位数对应的存储结构
vector<queue<int>> vq(10);
int k = 1;
while (k<=MAX_NUM)
{
//放入对应的基数中
for (int i = 0; i < n; i++) {
int x = GetDigit(arr[i], k);
vq[x].push(arr[i]);
}
//放回原数组
int pos = 0;
for (int i = 0; i < BASE_NUM; i++)
{
while (!vq[i].empty())
{
arr[pos++] = vq[i].front();
vq[i].pop();
}
}
k++;
}
//拍好的数组打印出来
print(arr, n);
return 0;
}基数排序的时间复杂度位O(kn)k为数字的最大位数，n为有多少数据