数据结构之排序算法

数据结构之数组排序（冒泡、选择、插入、快速）
一、冒泡排序法：
原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。因此，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度：
1.若数据初始状态是正序：O(n)
2.若初始文件是反序：O(n^2)
因此，平均时间复杂度为O(n^2)

代码实现：

public static void bubbleSort(int []arr) 
{    
	int[] arr = {5,3,4,7,9,2,1};      
	for(int i =0;i<arr.length-1;i++) 
	{        
		 for(int j=0;j<arr.length-i-1;j++)
		  {  
                   	 if(arr[j]>arr[j+1])
                   	  {       
	                             int temp = arr[j];         
	                      	arr[j]=arr[j+1];             
	              		arr[j+1]=temp;         
              		 }    
		 }    
	 } 
}

二、选择排序法：
原理：
1.从数组中找到最小的元素，和第一个位置的元素互换。
2.从第二个位置开始，找到最小的元素，和第二个位置的元素互换。
3.直到选出array.length-1个较小元素，剩下的最大的元素自动排在最后一位。
代码实现：

public static void selectSort(int []arr) 
{
	//给定无序数组
 	 int [] arr= {5,3,4,7,9,2,1};
 	 //先把0赋值给最小下标
 	 int minIndex = 0;
 	 //外循环从0到数组长度减一
	  for(int i=0; i<arr.length-1;i++)
	  {
   		//把i赋值给最小下标
  		 minIndex = i;
   		//内循环j从i+1开始循环到数组长度
   		for(int j=i+1; j<arr.length; j++)
  		 {
    			//拿开始定义的最小数和后面的数依次比较
    			if(arr[minIndex]>arr[j])
   			 {
     				//条件成立，交换下标
    				 minIndex = j;
			  }

 		  }
	   //如果下标交换
	   if(minIndex!=i)
	   {
	   	 //把两个值交换
	    	arr[minIndex] = arr[minIndex] + arr[i];
	    	arr[i] = arr[minIndex] - arr[i] ;
	   	 arr[minIndex] = arr[minIndex] - arr[i] ;

	   }
}

三、插入排序法
原理：
一般：从第一个元素开始，若当前元素i小于有序数组中的元素j，则从该元素开始将有序数组依次后移一位，并将当前元素i放置到该元素j位置。（插入）
简易：从有序数组最后一个元素开始，若当前元素i小于该元素j，则交换当前元素和该元素。

代码实现：

public static void insertSort(int []arr) 
{
	//给定无序数组
	int [] arr= {5,3,4,7,9,2,1};
	//从数组的第二个元素开始
	for(int i=1; i<arr.length; i++)
 	 {
 	 	//将第二个元素赋值给temp
 		  int temp = arr[i];
  		 int j = 0;
  		 // j从i-1开始
		 for(j=i-1;j>=0;j--)
		   {
		   	//和temp作比较
    			if(arr[j]>temp)
  			{
  				//赋值给arr[j+1]
     				arr[j+1] = arr[j];
   			}
   			 else
   			 {
    				 break;
  			 }
   		}
   	//如果上面arr[j]赋值给了arr[j+1]，将temp赋值给arr[j-1+1]
  	 if(arr[j+1]!=temp)
  	 {
    		arr[j+1] = temp;
  	 }
  }

四、快速排序法
原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现：

public static void quickSort(int[]arr,int low,int high)  
{   
	int i,j,temp,t;  
	if(low>high)   
	{    
		return;   
	}   
	i=low;   
	j=high;  	
	//temp就是基准位   
	temp = arr[low];   
	while(i<j)  
	 {    
	  	//先看右边，依次往左递减    
	  	while(temp<=arr[j]&&i<j)  
	    	{     
	    		j--;   
	    	 }   
	      	while (temp>=arr[i]&&i<j)
	       	{             
	           	i++;           
	          }
  	 	if (i<j) 
  	 	{              
  	   		t = arr[j];            
  	       		arr[j] = arr[i];      
  	                   arr[i] = t;       
  	         }
  	}
  	arr[low] = arr[i];  
         arr[i] = temp;  
         //递归调用左半数组 
         quickSort(arr, low, j-1);
	//递归调用右半数组    
	quickSort(arr, j+1, high);
 }