排序在干什么？
排序主要在干什么？主要是两件事：确定乱序数列中的某个数字到底在有序数列中应该处于哪个位置；在此基础上，让乱序数列中的其它数字尽可能的有序。
一.选择排序
作为一个普通人，脑回路大概率是这样：每次找到数列中最小的那个数，然后再从剩下的数中找到最小的数，依次这样找下去.......，这个过程叫做选择排序，过程用图表示的话大概就是这样：
但是这么做有个问题就是在找到数列中最小数的那个过程中，我们经历了太多次比较
例如，在找最小值2时，我们需要先拿着数列中的第一个数19跟后边的23比看看谁小，19小就再拿19跟7比较，一直要比到数列的最后一个数，对于图上这个13个数组成的数列，要想确定最小值是2就得比12次；拿走2后还要再继续重新找剩下数列中的最小值，就要找11次；.......找最小值的这个过程时间代价太大了，并且数列越长，时间开销越大，可以怎么优化这个过程吗？
我们分析一下选择排序干了什么事情？其实它只干了一件事情就是每次遍历这个乱序数列后都可以确定出在有序数列中一个数字的位置。比如第一次遍历后，可以确定出2一定位于有序数列的第一个位置，第二次遍历后可以确定出7一定位于有序数列的第二个位置.......但是除此之外，其他的数字还仍然是无序性质的，只能等到最后一次遍历完成后，整个数列才会突然变得有序。那我们能不能在第一次遍历的时候既可以确定某个数字在有序表中的实际位置，又能在经历第一次遍历后使乱序的数列变得有点有序呢？我们来看快速排序
选择排序代码实现：
# include<stdio.h>
void SelectSort(int arr[],int size){
for(int i=0;i<size;i++){
int min=arr[i];
int flag=i;
for(int j=i;j<size;j++){
if(arr[j]<min){
min = arr[j];
flag = j;
}
}
int temp = arr[i];
arr[i] = min;
arr[flag] = temp;
}
}
void PrintArr(int arr[],int size){
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}
}
int main(){
int arr[]={8,5,9,4,1,6,5,10};
int size = sizeof(arr)/sizeof(arr[0]);
SelectSort(arr,size);
PrintArr(arr,size);
}
在实际的代码实现中，比起直接开辟一个新的数列空间去存放新的有序数列（空间开销可能会很大），我们往往使用交换的方式来存放最小值，这样只需要记录最小值及最小值对应的下标，空间开销小得多。
二.快速排序
快速排序的基本步骤：
1.选择一个基准元素
2.将数组划分为两个子数组，左边子数组中的元素小于等于基准元素，右边子数组中的元素大于基准元素
3.对左边子数组和右边子数组递归地应用快速排序算法，直到子数组的长度为1或0
4.合并子数组，得到最终的有序数组。
对于步骤1、2，如果我们进行一次操作，相当于是遍历了一遍数组，过程如下：
经过一次遍历，我们不仅确定了19在有序数列中的位置就是位于两个子数组的连接处，而且还做到了让这个数列尽可能变得有序起来，这里得到的红色数列比起选择排序，除了已经确定位置的数字外，其他数字并不是完全的乱序，至少可以确定的是19左边的一堆数字一定比右边的那堆数字小。这样一来，比如15和23、25、27.....都不用再比大小，自然时间开销就短。
实现了一次遍历之后，怎么才能让整个数组都一步步变的有序呢？我们只需要在已经分割好的子数组中继续用上边的方法，以第一个绿色子数组为例，如果我们继续重复第一次遍历的步骤：先以7为基准元素，把比它小的放在7右，比它大的放在7左，这样我们就确定了7的位置，并且使这个小的子数组变得尽可能有序了，这时我们发现7d右边只有2一个数了，无法再次进行找基准元素然后分左右的操作，那么就说明7的右边的一个数是2，2的位置也唯一确定，就不用在管了，但是7左边的子数组还不是一个数，说明7右边的值都还不能唯一确定，那就继续找基准元素然后分左右，直到不能找基准元素分左右，也就是基准元素的左或右只有一个数，那么整个数列就有序了。那么对于19右边的子数列想要变得有序也该如此。
分治思想：
这个过程中，我们抽离出重复的步骤：1.找基准元素 2.分出基准元素的左数组和右数组
在重复的进行这个操作的过程中我们逐渐把一个长长的13个数的数列变成越来越短的数列，直到最后数列小到了只有一个数，最终解决了整个问题，这其中蕴含着分治思想。
分治就是把一个大的问题拆解成可以用同样的策略去解决的规模更小的问题，最后把这些解决好的小的问题的结果合并起来，就得到了我们要解决的大问题的结果。
快速排序代码实现：
# include <stdio.h>
int partition(int arr[],int low,int high){
int pivot = arr[low];
// 只要low和high不重合就一直执行该操作
while(low<high){
while(low<high&&arr[high]>=pivot){
high--;
}
arr[low] = arr[high];
while(low<high&&arr[low]<=pivot){
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
void QuickSort(int arr[],int low,int high){
if(low<high){
int pos = partition(arr,low,high);
QuickSort(arr,low,pos-1);
QuickSort(arr,pos+1,high);
}
}
对于快速排序的代码，我们需要首先写出如何将数列分成以基准元素为轴的两个子数组并确定出基准元素的位置，如何利用分治思想，只需要对这个过程进行递归调用就可以最终实现快速排序。
下边是一个快速排序过程讲解很清晰的up主，对递归或者具体代码实现过程不理解的同学请移步b站哈哈哈哈哈
全网最清晰快速排序，看完快排思想和代码全部通透，不通透你打我！_哔哩哔哩_bilibili
三.归并排序
归并排序的基本步骤：
1.一直对半划分原始数列，直至所有子数列长度为1
2.有序地合并原本无序的子数列
从上述步骤中就可以看出，归并排序的核心在于第二步
其中蓝色部分为步骤1
绿色部分为步骤2
分治思想：
第二步实现的核心在于分治思想，归并排序的思想如下：
这个算法的核心想法是：如果我可以将两个有序的子数列合并成一个有序的长数列，那么我就可以利用分治的思想，先把无序的长数列分割无限小后变成小的有序的子数列（子数列只有1个数时），把两个小的子数列合并成稍微长一点的有序子数列（结合第一个大图的绿色部分理解），再把稍微长一点的两个有序子数列合并成更长一点的有序数列......直到最后得到了想要的完全有序的完整数列。
归并排序的步骤1部分是完全无排序的，所以其实这部分的时间花费是完全浪费的，所以归并排序的时间复杂度也蛮高的。
归并排序代码实现：
# include <stdio.h>
# include <stdlib.h>
void Merge(int arr[],int tempArr[],int left,int mid,int right){
int i,j,k;
for(k=left;k<=right;k++){
tempArr[k] = arr[k];
}
for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++){
if(tempArr[i]<=tempArr[j]){
arr[k] = tempArr[i++];
}
else{
arr[k] = tempArr[j++];
}
}
while(i<=mid){
arr[k++]=tempArr[i++];
}
while(j<=right){
arr[k++]=tempArr[j++];
}
}
void MergeSort(int arr[],int tempArr[],int left,int right){
if(left<right){
int mid = (left+right)/2;
MergeSort(arr,tempArr,left,mid);
MergeSort(arr,tempArr,mid+1,right);
Merge(arr,tempArr,left,mid,right);
}
}
void PrintArr(int arr[],int size){
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}
}
int main(){
int* tempArr = (int*)malloc(10*sizeof(int));
int arr[]={8,5,9,4,1,6,5,10};
int size = sizeof(arr)/sizeof(arr[0]);
MergeSort(arr,tempArr,0,7);
PrintArr(arr,size);
}四.插入排序
插入排序的基本思想是将一个元素插入到已经排好序的部分中，直到整个数列有序
插入排序代码实现：
# include<stdio.h>
void InsertSort(int *arr,int size){
for(int i=0;i<size-1;i++){
int end = i;
int temp = arr[i+1];
while(end>=0){
if(arr[end]>temp){
arr[end+1]=arr[end];
end--;
}
else{
break;
}
}
arr[end+1] = temp;
}
}
void PrintArr(int arr[],int size){
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}
}
int main(){
int arr[]={8,5,9,4,1,6,5,10};
int size = sizeof(arr)/sizeof(arr[0]);
InsertSort(arr,size);
PrintArr(arr,size);
}六.冒泡排序
冒泡排序应该是我们接触的第一个排序算法，它的逻辑为：比较相邻的两个数，如果前面的数大于后面的数，则交换两数的位置，否则不交换，往后移动，比较接下来的两个数，这样经过一轮的遍历之后最大的数就会被换到数列最右边（倒数第一的位置）。下一次遍历时就会找到倒数第二大的数，被排在倒数第二的位置，以此类推.......
逻辑很简单，但是我在自己写的时候出现了数组越界的问题，所以还是记录一下这个算法的代码
我的错误代码如下：
for(int j=0;j<size;j++){ //取j<size 或 j<size-1均可
for(int i=0;i<size-j;i++){
if(arr[i+1]<arr[i]){举例说明问题：当我的数列大小为8时，i 会从0遍历到7，并比较 i 与 i+1 对应的数的大小，i<7时，不会出现问题，但是当 i =7 时，i+1 = 8，但是数组只能从arr[0] 到 arr[7] ，数组找不到arr[8]里的值，或者里边的值是垃圾值，则会影响数组排序。所以 i 的取值应该是从i = 0 到 size-j-1
冒泡排序代码实现：
以下是修改后的代码：
# include<stdio.h>
void BubbleSort(int arr[],int size){
for(int j=0;j<size-1;j++){
for(int i=0;i<size-j-1;i++){
if(arr[i+1]<arr[i]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
//交换相邻两个数
}
}
}
}
void PrintArr(int arr[],int size){
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}
}
int main(){
int arr[]={8,5,9,4,1,6,5,10};
int size = sizeof(arr)/sizeof(arr[0]);
printf("size is %d ",size);
BubbleSort(arr,size);
PrintArr(arr,size);
}