当前位置： 移动技术网 > IT编程>开发语言>Java > 荐 最普通的---》排序算法

荐 最普通的---》排序算法

2020年07月17日  | 移动技术网IT编程  | 我要评论

10 大排序算法只有以下 4 种是不稳定的：

快（快速排序）；

些（希尔排序）；

选（选择排序）；

堆（堆排序）。

快速排序

最差时间复杂度
 
每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
 
最优时间复杂度
 
每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
 
平均时间复杂度
 
 O(nlogn)
 
所需辅助空间 
主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
 
稳定性
 
不稳定

 

 

package sort;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		
		 int[] arr = new int[] {4,4,6,5,3,2,8,1};
	        int[] arr2 = new int[] {4,4,6,5,3,2,8,1};
	        quickSort(arr, 0, arr.length-1);
	        System.out.println(Arrays.toString(arr));
	        quickSort2(arr2, 0, arr.length-1);
	        System.out.println(Arrays.toString(arr2));
	}

	public static void quickSort(int[] arr,int startIndex,int endIndex) {
		//我们使用的是递归方式求解，所以必定有一个跳出递归的条件
		if(startIndex>=endIndex) {//当左索引与右索引重合或者大于时
			return;
		}
		int p=partition(arr,startIndex,endIndex);
		quickSort(arr,startIndex,p-1);
		quickSort(arr,p+1,endIndex);
		
	}
	public static int partition(int[] arr,int startIndex,int endIndex) {
		//取基准分割左右派，默认第一位为基准
		//跳出条件左索引与右索引相等时，说明分割完毕
		int p=arr[startIndex];
		int left=startIndex;
		int right=endIndex;
		while(left!=right) {
			//右指针开始向中间靠拢，直到找到最右部分小于基准的
			while(left<right&&arr[right]>p) {
				right--;
			}
			while(left<right&&arr[left]<=p) {
				left++;
			}
			if(left<right) {
				//将右部分小的数与左部找的大的数替换
				int temp=arr[left];
				arr[left]=arr[right];
				arr[right]=temp;
			}
			
		}
		//最后基准
		arr[startIndex]=arr[left];
		arr[left]=p;
		return left;
	}
	public static void quickSort2(int[] arr,int startIndex,int endIndex) {
		//我们使用的是递归方式求解，所以必定有一个跳出递归的条件
		if(startIndex>=endIndex) {//当左索引与右索引重合或者大于时
			return;
		}
		int p=partition(arr,startIndex,endIndex);
		quickSort2(arr,startIndex,p-1);
		quickSort2(arr,p+1,endIndex);
		
	}
	public static int partition2(int[] arr,int startIndex,int endIndex) {
		int p=arr[startIndex];
		int mark=startIndex;
		for(int i=startIndex+1;i<arr.length;i++) {
			if(arr[i]<p) {
				int temp=arr[i];
				arr[i]=arr[mark+1];
				arr[mark+1]=temp;
				mark++;
			}
		}
		arr[startIndex]=arr[mark];
		arr[mark]=p;
		return mark;
		
	}
}

选择排序

数据移动最少的

选择排序，设定开头元素为最小元素，循环遍历查找是否有新最小的元素可替换，前部有序区域逐渐变大
最差时间复杂度
 
O(n^2)
 
最优时间复杂度
 
O(n^2)
 
平均时间复杂度
 
O(n^2)
 
所需辅助空间 
O(1)
 
稳定性
 
不稳定

 

package sort;

import java.util.Arrays;

public class SelectionSort {
	 public static void main(String[] args) {
	        int[] arr = new int[] {4,4,6,5,3,2,8,1};
	        selectionSort(arr);
	        System.out.println(Arrays.toString(arr));
	    }
	 public static void selectionSort(int arr[]){
		 //每次循环找出最小元素放置当前循环次数位
		 for(int i=0;i<arr.length-1;i++) {
			 int min=i;
			 for(int j=i+1;j<arr.length;j++) {
				 //避免多次互换，每次找到小于当前循环次数位的值，只替换索引
				 if(arr[j]<arr[min]) {
					 min=j;
				 }
			 }
			 //比较索引是否更换，更换则找到最新最小值
			 if(min!=i) {
				 int temp=arr[min];
				 arr[min]=arr[i];
				 arr[i]=temp;
			 }
		 }
	 }

}

插入排序

适用：

  1. 数组每个元素距离它的最终位置都不远
  2. 一个有序大数组接一个小数组
  3. 数组中只有几个元素位置不正确

希尔排序是由插入排序进行优化

最差时间复杂度
 
最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
 
最优时间复杂度
 
最好情况为输入序列是升序排列的,此时时间复杂度O(n)
 
平均时间复杂度
 
O(n^2)
 
所需辅助空间 
O(1)
 
稳定性
 
稳定

 

package sort;

import java.util.Arrays;

public class InsertionSort {
	 public static void main(String[] args) {
	        int[] arr = new int[] {4,4,6,5,3,2,8,1};
	        insertionSort(arr);
	        System.out.println(Arrays.toString(arr));
	    }
	 public static void insertionSort(int arr[]){
		 //默认第一位元素为有序位，循环查找下一位在有序位的位置
		 for(int i=1;i<arr.length;i++) {
			 //记录下当前循环次数位置的值
			 int get=arr[i];
			 //当前位置的左部有序区起始索引
			 int j=i-1;
			 //循环有序区元素，边比对边将不适合元素后移
			 while(j>=0&&arr[j]>get) {
				 //将比对过的有序元素后移  j+1===i    
				 arr[j+1]=arr[j];
				 j--;
			 }
			 //跳出循环时表示找到比 比对元素 小的元素位置 j
			 //选择j的前一位 放置
			 arr[j+1]=get;
			 
		 }
	 }
}

希尔排序

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

各个子数组都很短，排序之后子数组都是部分有序（符合插入排序高性能时条件）。希尔排序就是调用若干趟插入排序。

最差时间复杂度
 
根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
 
最优时间复杂度
 
O(n)
 
平均时间复杂度
 
根据步长序列的不同而不同。
 
所需辅助空间 
O(1)
 
稳定性
 
不稳定

 

package sort;

import java.util.Arrays;

public class ShellSort {
	public static void main(String[] args) {
		int[] arr = new int[] {4,4,6,5,3,2,8,1};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
        int[] arr2 = new int[] {1,2,3,4,5,2,8,1};
        shellSort(arr2);
        System.out.println(Arrays.toString(arr2));
	}

	private static void shellSort(int[] arr) {
		for(int i=arr.length/2;i>0;i/=2) {
			System.out.println(i);
			shell(arr,i);
		}
		
	}

	private static void shell(int[] arr, int s) {

		int count=0;
		for(int i=s;i<arr.length;i=i+s) {
			count++;
			int get=arr[i];
			int j=i-s;
			while(j>=0&&get<arr[j]) {
				count++;
				arr[j+s]=arr[j];
				j=j-s;
			}
			arr[j+s]=get;
		}
		System.out.println(count);
		
	}

}

归并排序

分治法思想


 最差时间复杂度 ---- O(nlogn)
 最优时间复杂度 ---- O(nlogn)
 平均时间复杂度 ---- O(nlogn)
 所需辅助空间 ------ O(n)
 稳定性 ------------ 稳定

package sort;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = new int[] {4,4,6,5,3,2,8,1};
        mergeSort(arr,0,7);
        System.out.println(Arrays.toString(arr));
       
	}

	private static void mergeSort(int[] arr,int left,int right) {
		// TODO Auto-generated method stub
		//设置递归跳出条件,也就是当分割时左下标大于右下标,停止分割
		if(left>=right) {
			return;
		}
		int mid=(left+right)/2;
		mergeSort(arr,left,mid);
		mergeSort(arr,mid+1,right);
		merge(arr,left,right,mid);
		
	}

	private static void merge(int[] arr, int i, int j, int mid) {
		// TODO Auto-generated method stub
		//归并法的两部分比较可以想象成两支擂台队伍比赛，一个一个比，赢者，继续站在队伍中，失败者丢进废物队
		int [] temp=new int[(j-i)+1];//每两队比较所需要的暂存空间大小

		int index=0;
		int left=i;//左队起始
		int right=mid+1;//右队起始

		 //两队循环打擂台 大刘小走  记录两队比赛人员指针 左边开始
		while(left<=mid&&right<=j) {
			temp[index++]=(arr[left]<=arr[right])?arr[left++]:arr[right++];
		}
		
		//比完之后，也就是有一队伍的人都比较过了，可能有一队有个天降猛男擂台不倒，剩余队友直接丢进废物队吧哈哈
//把仍有留下的人直接加入暂存数组
		while(left<=mid) {
			temp[index++]=arr[left++];
		}
		while(right<=j) {
			temp[index++]=arr[right++];
		}

		//暂存空间数组复制至实际数组
        //暂存持久化
		for (int k = 0; k < temp.length; k++)
	    {
	        arr[i++] = temp[k];
	    }
		System.out.println(Arrays.toString(temp));
		
	}

}

 

本文地址：https://blog.csdn.net/weixin_42477252/article/details/107349659

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网