排序算法笔记

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

一：冒泡排序

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

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

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)/2
   int 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 
  }
}

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