排序算法分为交换类排序，插入类排序，选择类排序，归并类排序
交换排序分为 冒泡排序和快速排序
1.冒泡排序
1、思路：通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现前一个数大于后一个数则交换，使值较大的元素逐渐从前移向后部，就如果水底下的气泡一样逐渐向上冒。
2、先以一个数组讲解一下，然后再写代码：
待排序数组：3，9，-1，10，20
第一轮排序：
（1）3，9，-1，10，20 ----3跟9比较，不交换（2）3，-1，9，10，20 ----9比 -1大，所以9跟 -1交换
（3）3，-1，9，10，20 ----9跟10比较，不交换
（4）3，-1，9，10，20 ----10跟20比较，不交换
第一轮过后，将20这个最大的元素固定到了最后的位置。
在第二轮的时候20不参与冒泡。
第二轮排序：
因为20的位置已经固定，所以只对前4个进行排序即可：（1）-1，3，9，10，20 ----3比 -1大，进行交换
（2）-1，3，9，10，20 ----3跟9比较，不交换
（3）-1，3，9，10，20 ----9跟10比较，不交换
第二轮过后，将第二大的元素固定到了倒数第二个位置
第三轮排序：
10和20的位置已经确定，只需对前三个进行排序（1）-1，3，9，10，20 ----3和-1比较，不交换
（2）-1，3，9，10，20 ----3和9比较，不交换
第三轮过后，将第三大的元素位置确定
第四轮排序：
只对前两个元素进行排序（1）-1，3，9，10，20 ----3和-1比较，不交换
第四轮过后，将第四大的元素位置确定，此时总共5个元素，已经排序好4个，从而最后一个自然而然就是排好序的了
小结：
设总的元素个数为n，那么由上边的排序过程可以看出：（1）总计需要进行（n-1）轮排序，也就是（n-1）次大循环
（2）每轮排序比较的次数逐轮减少
（3）如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序
（4）时间复杂度是O(N^2) 在有序的时候，很快，因为有exchange变量优化了代码
#include<iostream>
using namespace std;
int a[20];
void swap(int &a,int &b)
{int temp=a;a=b;b=temp;
}void BubbleSort(int a[],int n)
{int i,j;bool flag;for(i=0;i<n-1;i++){flag=false;//每轮开始时初始化flag for( j=n-1;j>i;j--)//内层控制比较和交换 {if(a[j-1]>a[j]){swap(a[j-1],a[j]);flag=true;}}if(flag==false){break;}}
}int main()
{int n;cout<<"请输入数组的大小"<<endl;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}BubbleSort(a,n);for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;} 2.快速排序
1.思想：记第一个数为key，要调整key的位置，使得左边的都要比key的小，右边的数都比key的大。
2.步骤：
选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
还是定义一个left和一个right，left从左向右走（当遇到大于key的值时停下来）。right从右向左走（当遇到小于key的值时停下来）。（若在最左边挖坑，则需要right先走；若在最右边挖坑，则需要left先走）把right的那个小的数放在坑中，在把left那个位置的值放在right那个位置中
重复操作，直到left>right时结束，完成一趟，把key放在了正确的位置
最后用分治思想，分成左边和右边，递归。
#include<iostream>
using namespace std;int a[20]; int parttition(int a[],int low,int high)
{int pivot=a[low];//那最左边的作为分割值 while(low<high){while(low<high&&a[high]>pivot)//从后往前遍历，找到一个比分割值小的 high--;a[low]=a[high];while(low<high&&a[low]<pivot)low++;a[high]=a[low];}a[low]=pivot;return low;}
void quicksort(int *a,int low,int high)
{if(low<high){int pivot_pos=parttition(a,low,high);quicksort(a,low,pivot_pos-1);quicksort(a,pivot_pos+1,high);}
}
int main()
{int n;cout<<" element have ";cin>>n;for(int i=0;i<n;i++){cin>>a[i];}quicksort(a,0,n-1) ;for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
}插入排序
直接插入排序： 每次将一个记录按其关键字的大小插入到已经排好序的序列中，直至全部记录插入完毕。这种排序方式将待排数据依次和数组中已经排好序的记录进行比较并确定自己的位置。
假设现在有 10 个元素的整型数组：int arr[] = {16, 1, 45, 23, 99, 2, 18, 67, 42, 10}，现在，我们希望对这个数组中的元素进行从小到大排序。
根据直接插入排序算法的思想，我们首先认为数组中的第 1 个元素（16）包含在已经排好序的序列中。然后从数组中的第 2 个元素开始，依次针对数组中的元素寻找合适的位置插入到已经排好序的序列中就行了。
所以，就会有下面的操作步骤：
先看 1，1 比 16 小，所以 1 插入到 16 之前，16 后移。这是因为已经排好序的序列中目前只有 16，所以只需要将 16 后移，数组 arr 目前的情形是：{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。
接着看 45，45 比 1 和 16 都大所以 45 位置不动，数组 arr 目前的情形是：{1, 16, 45, 23, 99, 2, 18, 67, 42, 10}。
接着看 23，23 比 16 大但比 45 小，所以 23 插入到 45 之前，45 后移，数组 arr 目前的情形是：{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。
接着看 99，99 目前最大，所以位置不动，数组 arr 目前的情形是：{1, 16, 23, 45, 99, 2, 18, 67, 42, 10}。
接着看 2，2 比 1 大但比 16 小，所以 2 插入到 16 之前，16、23、45、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 23, 45, 99, 18, 67, 42, 10}。
接着看 18，18 比 16 大但比 23 小，所以 18 插入到 23 之前，23、45、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 45, 99, 67, 42, 10}。
接着看 67，67 比 45 大但比 99 小，所以 67 插入到 99 之前，99 后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 45, 67, 99, 42, 10}。
接着看 42，42 比 23 大但比 45 小，所以 42 插入到 45 之前，45、67、99 依次后移，数组 arr 目前的情形是：{1, 2, 16, 18, 23, 42, 45, 67, 99, 10}。
接着看 10，10 比 2 大但比 16 小，所以 10 插入到 16 之前，16、18、23、42、45、67、99 依次后移，数组 arr 目前的情形是：{1, 2, 10, 16, 18, 23, 42, 45, 67, 99}。
以上就是直接插入排序算法的完整工作过程描述。把一个无序数组 {16, 1, 45, 23, 99, 2, 18, 67, 42, 10} 最终变得有序 {1, 2, 10, 16, 18, 23, 42, 45, 67, 99}，只需要从前向后遍历数组中的每个元素，再为每个元素找到合适的位置就可以了。
————————————————
#include<iostream>
using namespace std;
int a[20];
//直接插入排序void InsertSort(int arr[], int len) {if (len <= 1) //不超过1个元素的数组，没必要排序return;for (int i = 1; i < len; i++) //从第2个元素（下标为1）开始比较{if (arr[i] < arr[i - 1]){int temp = arr[i]; //暂存arr[i]值，防止后续移动元素时值被覆盖 int j;//内层控制比较j要大于等于0，同时arr[j]大于temp时，arr[j] 位置元素向后覆盖 for (j = i - 1; j >= 0 && arr[j] > temp; j--) //检查所有前面排好序的元素{arr[j + 1] = arr[j]; //所有大于temp的元素都向后移动}arr[j + 1] = temp; //复制数据到插入位置，注意j因为被减了1，这里加回来}}return;
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}InsertSort(a,n);for(int i=0;i<n;i++){cout<<a[i]<<" "; }return 0;} 选择排序：简单选择排序 堆排序 数排序
选择排序
//简单选择排序
void SelectSort(int *a,int len)
{int i,j;for( i=0;i<len-1;i++)// {int min=i;for(j=i;j<len;j++){if(a[j]<a[min]){min=j;}}swap(a[i],a[min]);}} 堆排序：除了快排接着就是堆排序会在初试中出大题和选择题所以很重要
假设我们有10个元素，将这十个元素建成一个完全二叉树这里采用层次建树法，我们将二叉树中的任意一个位置的元素对应到数组下标上，我们将二叉树中每个元素对应到数组下标的这种数据结构称为堆，比如最后一个父元素的下标是N/2-1,也就是a[4],还有如果父亲节点的下标是dad,那么父节点对应的左子节点的下标值是2*dad+1.接着将每颗子树都调整为父节点最大，最终将整棵树变为一个大根堆。变成大根堆之后，将第根节点和最后一个节点元素值交换，再接着调整成大根堆，直到最后。
#include<iostream>
using namespace std;
int a[20];void swap(int &a,int &b)
{int temp=a;a=b;b=temp;}
//直接插入排序void InsertSort(int arr[], int len) {if (len <= 1) //不超过1个元素的数组，没必要排序return;for (int i = 1; i < len; i++) //从第2个元素（下标为1）开始比较{if (arr[i] < arr[i - 1]){int temp = arr[i]; //暂存arr[i]值，防止后续移动元素时值被覆盖 int j;//内层控制比较j要大于等于0，同时arr[j]大于temp时，arr[j] 位置元素向后覆盖 for (j = i - 1; j >= 0 && arr[j] > temp; j--) //检查所有前面排好序的元素{arr[j + 1] = arr[j]; //所有大于temp的元素都向后移动}arr[j + 1] = temp; //复制数据到插入位置，注意j因为被减了1，这里加回来}}return;
} //简单选择排序 void SelectSort(int* a, int n)
{for (int i = 0; i < n-1; i++)//i<n-1当它是最后一个数的时候不需要进行交换排序{int min = i;//min记录最小元素的下标 int j;for (j = i; j < n; j++){if (a[j] < a[min]){min=j;}}swap(a[i], a[min]);}
}
//把某个子树调整为大根堆
void AdjustDown(int *a,int k,int len)
{int dad=k;//父亲的下标int son=2*k+1;//左孩子的下标while(son<len){if(son+1<len&&a[son]<a[son+1])//如果左孩子小于右孩子 {son++;//拿右孩子和dad比 }if(a[son]>a[dad]){swap(a[son],a[dad]); dad=son;//son重新作为dad，去判断下面的子树是否符合大根堆son=2*dad+1; } else{break;}}
}void HeapSort(int *a, int len)
{int i;//就是把堆调整为大根堆 for(i=len/2-1;i>=0;i--) {AdjustDown(a,i,len);}swap(a[0],a[len-1]);//交换根部元素和最后一个元素for(i=len-1;i>0;i--){AdjustDown(a,0,i);//调整剩余元素变为大根堆swap(a[0],a[i-1]); //交换根部元素和无序数组的最后一个元素 } }
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}//InsertSort(a,n);//SelectSort(a,n);HeapSort(a,n);for(int i=0;i<n;i++){cout<<a[i]<<" "; }return 0;} 归并排序
思路：
1.不断的分割数据，让数据的每一段都有序（一个数据相当于有序）
2.当所有子序列有序的时候，在把子序列归并，形成更大的子序列，最终整个数组有序。
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)//在这个函数中调用递归{if (left >= right){return;}int mid = (left + right) >> 1;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid+1, right, tmp);//合并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = left; j <= right; j++){a[j] = tmp[j];}
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
