记录一下学习的排序算法及代码实现，和个人笔记。

一：冒泡排序

如果遇到相等的值不进行交换，那这种排序方式是稳定的排序方式。

原理：比较两个相邻的元素，将值大的元素交换到右边

void BubbleSort(int arr[],int size)
{ //冒泡排序 两个for循环  内层为size-i-1//时间复杂度O(n^2)  无论好坏都要遍历完整个数组 for(int i=0;i<size;i++){for(int j=0;j<size-i-1;j++){if(arr[j+1]<arr[j]) //如果后面的值比前一个大则交换{swap(arr[j+1],arr[j]);}}     }
}

二：选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

时间复杂度：O(n^2)

void SelectSort(int arr[],int size) 
{//选择排序   每次找数组中的最小值的索引  一轮后交换 for(int i=0;i<size-1;i++){  int index=i;  //最小值索引 for( int j=i+1;j<size;j++) {if(arr[j]<arr[index]) //j++  往右找比索引值小的 {index=j; //找到的值如果比当前索引值小就更新index }} swap(arr[index],arr[i]); //内层循环完找到真的最小值索引 与i交换 //这样可以省去多次交换 每次内层交换一个	}		
}

三：插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动，该算法是稳定的。

时间复杂度：O(n^2)

void InsertSort(int arr[],int size)
{//插入排序  最坏时间复杂度为O(n^2)   逆序时   4321 // 最好时间复杂度为O(n)    已经有序时    1234 for(int i=1;i<size;i++) //第一个默认有序 {for(int j=i-1;j>=0&&arr[j+1]<arr[j];j--){//从右往前看  如果后面的数小于当前已经有序的最后一个就交换//然后依次往前	 为0 或者不小于前一个数就退出 swap(arr[j+1],arr[j]);} 	}} 

四：快速排序

分治思想+填坑法

初学暂时选第一个为基准数  可能受数据情况影响最差会退化为冒泡排序   不稳定排序

void QuickSort(int arr[],int start,int end)
{  
//快速排序  挖坑法  平均时间复杂度为 O(N*log2N) 二为底的对数N int i=start;int j=end;int tmp=arr[start];//基准数if(i>=j) return;//递归停止条件 while(i<j){  //从右往左找比基准数小的 while(i<j&&arr[j]>=tmp)	{j--; //大于等于基准数就左移 }//填坑if(i<j){arr[i]=arr[j]; //填完左边 i得右移 i++;} //从左往右找比基准数大的while(i<j&&arr[i]<tmp){i++; //如果小于就一直i++找	} //填坑if(i<j){arr[j]=arr[i];j--;}}arr[i]=tmp; //填基准数 QuickSort( arr,start,i-1);  //递归左边 QuickSort( arr,i+1,end) ;    //递归右边 
}

五：归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并，是稳定排序算法。

平均时间复杂度：O(nlogn)      空间复杂度：T(n)

void merge(int arr[],int left,int mid,int right)
{int tmp[right-left+1]; //定义一个临时数组  长度为right-left+1 //注意长度为下标加一 int i=0;  //额外数组的索引 int p1=left; //左索引 int p2=mid+1; //右索引为中位值+1 while(p1<=mid&&p2<=right) //当两个都还有元素要排序 {tmp[i++]=(arr[p1]<=arr[p2])?arr[p1++]:arr[p2++];//从两个数组中（一个数组看成两个）选取小的值 传给临时数组 更新索引 }while(p1<=mid) //此时后半段p2结束 {tmp[i++]=arr[p1++]; //只复制前面p1 }while(p2<=right) //这个情况前半段结束  {tmp[i++]=arr[p2++]; //只要把剩余的p2复制过去 }for(int k=0;k<right-left+1;k++)  //把排好序的临时数组赋值回原来的数组 {arr[left+k]=tmp[k]; //注意起点是left  因为不是0(变化) }	}//归并排序  时间复杂度为 N*logN  稳定排序 //分治思想  额外空间复杂度O(N) 
void mergeSort(int arr[],int left,int right)
{  if(left<right) //递归停止条件 {int mid=left+(right-left)/2; //防溢出   ? 这里不能使用>>1 mergeSort(arr,left,mid);  //递归左边排好序 mergeSort(arr,mid+1,right); //递归右边排好序 merge(arr,left,mid,right);  //合起来排序 }
} 

六：堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)，是不稳定的排序算法。

//堆排序  o(nlogn)  不稳定 //维护堆的性质  o(logn)
// 存储堆的数组 arr   数组长度n  待维护的节点下标index
void heapify(int arr[],int n,int index) 
{int largest=index; //先初始化默认父节点最大  (i-1)/2int lson=2*index+1; //左孩子2*i+1 int rson=2*index+2;  //右孩子 2*i+2 /* if(rson<n){largest=max(largest,max(lson,rson));  //拿索引比较错误了 }*///找到最小值 if(rson<n && arr[largest]<arr[lson])  //这里比的是值  {//限制左孩子不能超出数组范围 largest=lson; }if(rson<n && arr[largest]<arr[rson]) {largest=rson;}if(largest!=index){swap(arr[largest],arr[index]); //大的值要交换上去 heapify(arr,n,largest); //递归维护 }}
//堆排序入口 
void heapSort(int arr[],int n)
{//建堆  时间复杂度为 o（n） int i;for(int i=(n-1)/2;i>=0;i--){heapify(arr,n,i);}	 	//排序 从最右端开始倒序交换 //每次都取出当前的根节点arr[0]  然后维护住堆的性质 for(int i=n-1;i>=0;i--){cout<<arr[0]<<" ";swap(arr[i],arr[0]); //交换根节点和最后一个元素 heapify(arr,i,0); //这里的数组长度传i  依次减小到0 }
}

暂时学到堆排序，排序算法告一段落~~~