1.冒泡排序法
英文:bubble sort ????(bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置
每一轮比较会让一个最大数字沉底或者一个最小数字上浮
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
从小到大：
#include <iostream>
using namespace std;
//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
int temp;
for (int i = 0; i < len - 1; ++i)//循环比较次数
{
//for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
{
if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
{
//交换两个元素位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:" ;
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
bubble_sort(arr, 10);
cout << endl << "排序后数组：";
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
}
排序前数组:25 25 1 7 8 19 289 25 46 93
排序后数组:1 7 8 19 25 25 25 46 93 289
2.选择排序法
它的工作原理是 每一次从待排序的数据元素中 选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
#include <iostream>
using namespace std;
//从小到大：
void select_sort(int arr[], int len)//选择排序
{
int k, temp;
for (int i = 0; i < len - 1; ++i)//选出arr[i]这个位置的元素
{
k = i;//保存这个位置的下标 作为初始条件
for (int j = i + 1; j < len; ++j)//找后面所有元素
{
if (arr[k] > arr[j])
{
k = j; // arr[j]更小 用k保存位置
}
}
//找完之后 交换arr[i] arr[k]
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:" ;
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
select_sort(arr, 10);
cout << endl << "排序后数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
}
排序前数组:25 25 1 7 8 19 289 25 46 93
排序后数组:1 7 8 19 25 25 25 46 93 289
3.直接插入排序
基本操作就是：将
有序数据后的第一个元素插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据
算法解释：（从小到大）
算法三个步骤：
先保留要插入的数字
往后移
插入元素
#include <iostream>
using namespace std;
//从小到大：
void insert_sort(int arr[], int len)
{
int temp;
for (int i = 1; i < len; ++i)//从第二个人开始插入 i的值相当于有序的个数
{
//先找合适的位置
for (int j = 0; j < i; ++j)
{
if (arr[j] > arr[i]) // 找比arr[i]要大的第一个元素
{
//要将 arr[i] 插入到arr[j]的位置
temp = arr[i];//先保留要插入的数字
for (int k = i - 1; k >= j; --k)
{
arr[k + 1] = arr[k];//往后移
}
arr[j] = temp;//插入元素
break;//插入之后直接退出(第一个for)循环
}
}
}
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:" ;
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
insert_sort(arr, 10);
cout << endl << "排序后数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
}
排序前数组:25 25 1 7 8 19 289 25 46 93
排序后数组:1 7 8 19 25 25 25 46 93 289
4.快速排序
4.1用递归实现
它的基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比 另外一部分的所有数据 都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#include <iostream>
using namespace std;
int part(int arr[], int begin, int end)
{
//1.选中arr[begin]作数字
int temp;
int i = begin, j = end; //begin不能+1，因为不能保证begin+1<end
while (i < j)
{
//从右边找到一个比arrr[begin]小的元素
while (i<j && arr[j]>arr[begin]) --j;//找一个比arr[begin]要小的元素
//从左边找到一个比arrr[begin]大的元素
while (i < j && arr[i] <= arr[begin]) ++i;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;//交换元素
}
//退出来的时候 i==j的 并且arr[i]这个位置 就是要找的k
//arr[begin] 和arr[i]交换
temp = arr[begin];
arr[begin] = arr[i];
arr[i] = temp;
return i;
}
void quick_sort(int arr[], int begin, int end)
{
if (begin >= end) return;
//begin必须小于end才需要排序
//1.分成两个部分
int k = part(arr, begin, end);//分成两个部分
//arr[k]左边的元素全部小于arr[k] arr[k]右边元素全部大于arr[k]
//2.排序左边
quick_sort(arr, begin, k - 1);//k的位置不参与排序 所以是k-1
//3.排序右边
quick_sort(arr, k + 1, end);
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:" ;
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
quick_sort(arr,0,9);
cout << endl << "排序后数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " " ;
}
排序前数组:25 25 1 7 8 19 289 25 46 93
排序后数组:1 7 8 19 25 25 25 46 93 289
5.归并排序
排序原理：
- 尽可能的将一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
- 将相邻的两个子组进行合并成一个有序的大组；
- 不断的重复步骤2，直到最终只有一个组为止。
#include<iostream>
#include<iomanip>
using namespace std;
int a[101];
//这一步是合并两个数组的过程，数组的范围分别是[left,mid][mid+1,right]
void Merge(int* arr, int left, int mid, int right)
{
int* temp = new int[right - left + 1]; //申请一个空间来存放合并好的数组(后面需要销毁)
int st1 = left; //这里是数组1的开始位置
int st2 = mid + 1; //这里是数组2的开始位置
int t = 0; //合并数组的开始位置
//这里结束的条件是一个数组已经放进去完了
while (st1 <= mid && st2 <= right)
{
//从开始位置比较，如果数组1的元素大于数组2，则将数组2的元素存进去一个，然后位置+1，否则相反
temp[t++] = arr[st1] < arr[st2] ? arr[st1++] : arr[st2++];
}
while (st1 <= mid) { //如果是st1没有放完就直接放在最后面
temp[t++] = arr[st1++];
}
while (st2 <= right) { //如果是st2没有放完就直接放在最后面
temp[t++] = arr[st2++];
}
//这里把临时创建的数组拷贝到原来的数组中
for (int j = 0; j < t; ++j) {
arr[left + j] = temp[j];
}
delete[] temp; //销毁临时变量
}
void MergeSort(int* arr, int start, int end) {
if (arr == NULL || start >= end)
return;
if (start < end)
{
int mid = (start + end) / 2; //找到每个分块的中间值
MergeSort(arr, start, mid); //左边递归进行分离和合并
MergeSort(arr, mid + 1, end); //右边递归进行分离和合并
Merge(arr, start, mid, end); //左右合并
}
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
MergeSort(arr, 0, 9);
cout << endl << "排序后数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
}
6.希尔排序
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。
算法思想
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
- 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
代码实现：
#include<iostream>
#include<iomanip>
using namespace std;
//从小到大
void shellSort(int* arr, int n)
{
int gap, i, j, temp;
//小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
for (gap = n / 2; gap >= 1; gap = gap / 2)
{
//**********************************直接插入排序（只是步长改变）**************************************************
//因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
for (i = gap; i < n; i++)
{
if (arr[i] < arr[i - gap])
{
temp = arr[i];
//后移
for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
{
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;//插入进去
}
}
//************************************************************************************
}
}
int main()
{
int arr[] = { 25,25,1,7,8,19,289,25,46,93 };
cout << "排序前数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
shellSort(arr,10);
cout << endl << "排序后数组:";
for (int i = 0; i < 10; i++)
cout << arr[i] << " ";
}