几种常见的排序步骤及时间复杂度

几种常见的排序方法及时间复杂度

在学习JAVA中遇到几个从前不是很理解的排序方法，拿出来和大家分享分享哈

1.冒泡排序（又称下沉排序）

public class BubbleSort 
{
	public static void main(String[] a)
	{
		int[] list={2,9,5,4,8,1};

		System.out.println("Before bubble sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}
		
		bubbleSort(list);
		
		System.out.println("\nAfter bubble sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}		
	}
	 
	private static void bubbleSort(int[] list)
	{
		boolean needNextPass=true;
		
		for(int k=1;k<list.length;k++)
		{
			//数组可能已经排好序
			needNextPass=false;
			
			for(int i=0;i<list.length-k;i++)
			{
				//交换list[i]和list[i+1]
				if(list[i]>list[i+1])
				{
					int temp=list[i];
					list[i]=list[i+1];
					list[i+1]=temp;
					
					needNextPass=true;
				}
			}
		}
	}
}

冒泡排序之时间复杂度：最差情况下，第一次冒泡排序需要n-1次遍历，第二次需要n-2次遍历，以此类推。。。因此，比较总数为：(n-1)+(n-2)+....+1=n²/2-n/2.

从而，冒泡排序的最差时间是O（n²） 。

2.归并排序

 public class MergeSort
{
	public static void main(String[] a)
	{
		int[] list={2,9,5,4,8,1,6,7,3};
		
		System.out.println("Before merge sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}
		
		mergeSort(list);
		
		System.out.println("\nAfter merge sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}
	}
	
	private static void mergeSort(int[] list)
	{
		if(list.length>1)
		{
			int[] firstHalf=new int[list.length/2];
			System.arraycopy(list, 0, firstHalf, 0, list.length/2);
			mergeSort(firstHalf);//递归算法
			
			int secondHalfLength=list.length-list.length/2;
			int[] secondHalf=new int[secondHalfLength];
			System.arraycopy(list, list.length/2, secondHalf, 0,secondHalfLength );
			mergeSort(secondHalf);//递归算法
			
			int[] temp=merge(firstHalf,secondHalf);
			System.arraycopy(temp, 0, list, 0, temp.length);
		}
	}
	
	private static int[] merge(int[] list1,int[] list2)
	{
		int[] temp=new int[list1.length+list2.length];
		
		int current1=0;//Index in list1
		int current2=0;//Index in list2
		int current3=0;//Index in temp
		
		while(current1<list1.length&&current2<list2.length)
		{
			if(list1[current1]<list2[current2])
				temp[current3++]=list1[current1++];
			else
				temp[current3++]=list2[current2++];
		}
		
		while(current1<list1.length)
			temp[current3++]=list1[current1++];
		
		while(current2<list2.length)
			temp[current3++]=list2[current2++];
		
		return temp;
	}
}

归并排序之时间复杂度： T(n)=T(n/2)+T(n/2)+mergetime .其中T(n/2)是对数组的前半部分排序所需时间，而第二项T(n/2)是对数组的后半部排序所需的时间。要将两个子数组归并最多要n-1次比较两个子数组中的元素，以及n次移动将元素移到临时数组中。故总时间为2n-1。

T(n)=2T(n/2)+2n-1=2(2T(n/4)+2*(n/2)-1)+2n-1=.....=2nlogn+1=O(nlogn)

3.快速排序

public class quickSort
{
	public static void main(String[] a)
	{
		int[] list={5,2,9,3,8,4,0,1,6,7};
		
		System.out.println("Before quick sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}
		
		quickSort(list);
		
		System.out.println("\nAfter quick sort:");
		for(int i=0;i<list.length;i++)
		{
			System.out.print(list[i]+" ");
		}
	}
	
	private static void quickSort(int[] list)
	{
		if(list.length>1)
		{
			quickSort(list,0,list.length-1);
		}
	}
		
	private static void quickSort(int[] list,int first,int last)
	{	
		if(last>first)
		{
			int pivotIndex=partition(list,first,last);
			quickSort(list,first,pivotIndex-1);
			quickSort(list,pivotIndex+1,last);
		}
	}
	
	private static int partition(int[] list,int first,int last)
	{
		//将第一个元素作为主元（pivot）
		int pivot=list[first];
		
		//向前遍历的索引，开始时指向第二个元素
		int low=first+1;
		
		//向后遍历的索引,开始时指向数组最后一个元素
		int high=last;
		
		while(high>low)
		{
			//从左开始向前遍历
			while(low<=high&&list[low]<=pivot)
				low++;
			//从右开始向后遍历
			while(low<=high&&list[high]>pivot)
				high--;
			
			//交换数组中的两个元素
			if(high>low)
			{
				int temp=list[high];
				list[high]=list[low];
				list[low]=temp;
			}
		}
		
		while(high>first&&list[high]>=pivot)
			high--;
		
		//和list[high]交换主元
		if(pivot>list[high])
		{
			list[first]=list[high];
			list[high]=pivot;
			return high;
		}
		else
			return first;
	}
}

快速排序之时间复杂度：还请各位高手指点我，在下先3Q啦

几种常见的排序步骤及时间复杂度

相关推荐