时间戳

首页 > 技术文章 > 常见排序算法——七大比较类排序算法

常见排序算法——七大比较类排序算法

bluemapleman 2018-07-07 11:30 原文

|算法|最坏复杂度|平均复杂度|最好复杂度|空间复杂度|稳定性|
|--|--|--|--|--|
|选择排序|O($n2$)|O($n2$)|O($n^2$)|O(1)|不稳定|
|插入排序|O($n2$)|O($n2$)|O($n$)|O(1)|稳定|
|希尔排序|O($nlog(n))$~O($n2$)|O($n{1.3}$)|O($n^2$)|O(1)|不稳定|
|冒泡排序|O($n2$)|O($n2$)|O(n)(用交换flag改进)|O(1)|稳定|
|快速排序|O($n^2$)|O($nlog(n)$)|O($nlog(n)$)|O(log(n))~O(n)|不稳定|
|堆排序|O($nlog(n)$)|O($nlog(n)$)|O($nlog(n)$)|O(1)|不稳定|
|归并排序|O($nlog(n)$)|O($nlog(n)$)|O($nlog(n)$)|O(n)|稳定|

Java实现

选择排序

//选择排序：每次遍历找到数组中的最小值，放到剩余数组最前面，以此类推，直到所有元素被排好
	public static void select_sort(int[] arr){
		int len=arr.length;
		long start=System.currentTimeMillis();
		for(int i=0;i<len;i++){
			for(int j=i+1;j<len;j++){
				if(arr[i]>arr[j]){
					swap(arr,i,j);
				}
			}
		}
		long end=System.currentTimeMillis();
		System.out.println("选择排序耗时（秒）："+(end-start));
		//toPrint(arr);

	}

插入排序

//插入排序:用新的元素去与已经排序好的元素数组从尾部开始比较，若比对应元素小，则下标继续往前走，直到找到比新元素小的元素，然后将比新元素小的元素后面的全部元素后移，插入新元素。
public static int[] insert_sort(int[] arr){
		long start=System.currentTimeMillis();
		for(int i=0;i<arr.length;i++){
            int temp=arr[i];
            for(int j=i;j>0 && arr[j-1]>arr[j];j--){
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }		
		long end=System.currentTimeMillis();
		System.out.println("插入排序耗时（秒）："+(end-start));
        return arr;
		//toPrint(temparr);
	}

希尔排序

//希尔排序:以arr.length/2为开始间隔，并不断/2缩小间隔的插入排序，最后一次的循环比较e就是插入排序，但是数组的绝大部分元素已经处于相对有序状态。
public static int[] shell_sort(int arr[]){
		for(int gap=arr.length; gap>0 ; gap/=2){
			for(int i=gap;i<arr.length;i++){
				int temp=arr[i];
				for(int j=i;j>=gap && arr[j-gap]>arr[j];j-=gap){
					arr[j]=arr[j-gap];
					arr[j-gap]=temp;
				}
			}
		}
		return arr;
	}

冒泡排序

//冒泡排序：比较相邻两个元素的大小，决定是否交换位置，每次循环可将一个最大值元素一直交换到最后面(或者将最小值一直交换到最前面)，以此类推。用一个交换flag作优化可以将最优情况时间复杂度降到O(n)，即只比较一轮。
public static void bubble_sort(int[] arr){
	int len=arr.length;
	long start=System.currentTimeMillis();
	boolean swapFlag=true;
	for(int i=0;i<len;i++){
		if(swapFlag==false)
			break;
		swapFlag=false;
		for(int j=1;j<len-i;j++){
			if(arr[j-1]>arr[j]){
				swap(arr,j-1,j);
				swapFlag=true;
			}
		}
	}

快速排序

//思路：每一次排序，将首元素(arr[0])交换到这样的位置，即它所在位置往右的所有元素都不小于它，且它所在位置往左的所有元素都不大于它。完成这一步，只需要将首元素不断地从右往左遍历找比它小的，然后从左往右找比它大的，找到即交换位置，一直到从两个方向都再也找不到一个可以交换的元素，一轮排序结束。接着用递归的方式排序剩下的两半。
public static void quickSort(int[] arr,int start,int end){
		if(start>=end)
			return;
		
		boolean leftFlag=false,rightFlag=false;
		
		int pivot=start;
		System.out.println("hehe");
		while(!(leftFlag && rightFlag)){
			leftFlag=true;rightFlag=true;
			//第一轮：第一个元素从右边开始找第一个比它小的元素，与之交换位置
			for(int i=end;i>=start;i--){
				if(arr[pivot]<arr[i]){
					exchange(arr, pivot, i);
					pivot=i;
					leftFlag=false;
				}
			}
			System.out.println("循环");
			for(int i=start;i<=end;i++){
				if(arr[pivot]<arr[i]){
					exchange(arr, pivot, i);
					pivot=i;
					rightFlag=false;
				}
			}
		}
		
		quickSort(arr, start, pivot-1);
		quickSort(arr, pivot+1,end);
		
	}

堆排序

归并排序

//思路：将数组不断划分为更小的两个数组的组合（递归），当划分到最小的粒度时，即两个数之间的比较与位置交换，然后不断将两个小的数组融合成大的数组(merge方法)。
public static void merge_sort(int[] arr,int low,int high){
		if(high>low){
			int pivot=(high+low)/2;
			merge_sort(arr,low,pivot);
			merge_sort(arr,pivot+1,high);
			merge(arr,low,pivot,high);
		}
	}
	
	private static void merge(int[] arr,int low,int pivot,int high){
		int[] temp=new int[high-low+1];
		int i=low,j=pivot+1;
		int count=0;
		while(i<=pivot && j<=high){
			if(arr[i]>arr[j]){
				temp[count++]=arr[j];
				j++;
			}
			else{
				temp[count++]=arr[i];
				i++;
			}
		}
		
		while(i<=pivot){
			temp[count++]=arr[i];
			i++;
		}
		
		while(j<=high){
			temp[count++]=arr[j];
			j++;
		}
		for(int x=0;x<temp.length;x++){
			arr[low+x]=temp[x];
		}
	}

推荐阅读