排序算法总结 java

冷不防 2022-09-11 08:26 3阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>平均时间复杂度</th> 
   <th>最好情况</th> 
   <th>最坏情况</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlog<sup>2</sup>n)</td> 
   <td>O(nlog<sup>2</sup>n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n<sup>s</sup>)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(logn)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

## 冒泡排序 ##

1.  比较相邻两个元素，如果no.2 < no.1，就交换两个元素。
2.  对每一对相邻元素进行一样的操作，从第一对一直到结尾的最后一对。
3.  针对所有元素重复上述步骤，除了最后一个。

public class MaoPao {
        
    	public static void main(String[] args) {
        
    		int[] arr = new int[]{
        3,9,-1,10,2};
    		bubblesort(arr);
    		System.out.println(Arrays,toString(arr));
    	}
    	public static int[] bubblesort(int[] arr) {
        
    		if (arr == null || arr.length < 2) return arr;
    		int n = arr.length;
    		for (int i = 0; i < n; i++) {
        
    			boolean flag = true;
    			for (int j = 0; j < n-i-1; j++) {
        
    				if (arr[j] > arr[j+1]) {
        
    					flag = false;
    					int temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    				}
    			}
    			//flag = true证明数组已经是按顺序排序了，一次交换也没有，可以直接退出循环。
    			if (flag) {
        
    				break;
    				}
    		}
    		return arr;
    	}
    }

## 选择排序 ##

1.  在数组中找到最小的元素， 将它与第一个元素进行交换
2.  在剩下的元素中找到最小的元素，与第二个元素交换

public class SelectSort {
        
    	public static void main(String[] args) {
        
    		int[] arr = new int[]{
        3,0,-9,1,2};
    		selectsort(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    	public static int[] selectsort(int[] arr) {
        
    		int n = arr.length;
    		for (int i = 0;i < n-1;i++) {
        
    			//假设第一个元素是最小的。
    			int min = i;
    			for (int j =i+1; j < n; j++) {
        
    				if (arr[j] < arr[min]) {
        
    					min = j;
    				}
    			}
    			//证明第一个元素不是最小的，交换
    			if (i != min) {
        
    				int temp = arr[min];
    				arr[min] = arr[i];
    				arr[i] = temp;
    			}
    		}
    		return arr;
    	}
    }

## 插入排序 ##

1.  将数组看作一个有序表和一个无序表，开始的时候，有序表中只有一个元素，无序表是除了第一个元素剩下的所有元素。
2.  排序过程中，每次从无序表中抽出第一个元素，与有序表进行比较，插入到合适的位置。

public class InsertSort {
        
    	public static void mian(String[] args) {
        
    		insertsort(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    	public static int[] insertsort(int[] arr) {
        
    		for (int i = 1; i < arr.length;i++) {
        
    			int temp = arr[i];
    			int j = i-1;
    			while (j >= 0 && temp < arr[j]) {
        
    				//有序表扩大，大的元素放在后面
    				arr[j+1] = arr[j];
    				// 向前移，比较有序表之前的元素和当前元素的大小
    				j--;
    			}
    			//此时j=-1，
    			//或者temp>arr[j] 
    			arr[j+1] = temp;
    		}
    		return arr;
    	}
    }

## 希尔排序 ##

public class ShellSort {
        
    	public static void main(String[] args) {
        
    		int[] arr= new int[]{
        8,9,1,7,2,4,5,3,6,0};
    		shellsort(arr);//交换
    		shellmove(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    	//这是希尔排序的交换法
    	public static int[] shellsortexchange(int[] arr) {
        
    		for (int gap = arr.length/2 ;gap > 0; gap /=2) {
        
    			for (int i = gap; i < arr.length; i++) {
        
    				for (int j = i-gap; j >= 0;j -= gap) {
        
    					if (arr[j] > arr[j+gap]) {
        
    						int temp = arr[j];
    						arr[j] = arr[j+gap];
    						arr[j+gap] = temp;					
    					}
    				}
    			}
    		}
    		return arr;
    	}
    	public static int[] shellsortmove(int[] arr) {
        
    		for (int gap = arr.length/2; gap > 0; gap /= 2) {
        
    			for (int i = gap; i < arr.length; i++) {
        
    				int j = i;
    				int temp = arr[j];
    				if(arr[j] < arr[j-gap]) {
        
    					while (j-gap >= 0 && temp < arr[j-gap]) {
        
    						//移动
    						arr[j] = arr[j-gap];
    						j -= gap;
    					}
    					arr[j] = temp;
    				}
    			}
    		}
    		return arr;
    	}
    }

## 归并排序 ##

归并排序是用归并的思想实现的排序方法，该算法采用经典的分治策略，分：将问题分为小的问题递归求解；治：将分的阶段得到的答案修补。  
![在这里插入图片描述][fd7c285a5b674ba0a33dc94e716c65fe.png]

public static int[] mergosort(int[] arr,int left,int right) {
        
    	if (left < right) {
        
    		int mid = (left + right) / 2;
    		arr = mergosort(arr,left,mid);
    		arr = mergosort(arr,mid+1,right);
    		mergo(arr,left,mid,right);
    	}
    	return arr;
    }
    public static void mergo(int[] arr,int left, int mid,int right) {
        
    	int[] str = new int[right-left+1];
    	int l = left;
    	int j = mid+1;
    	int k = 0;
    	while (l < j && j <= right){
        
    		if (arr[l]< arr[j]) {
        
    			str[k] = arr[l];
    			k++;
    			l++;
    		}else {
        
    			str[k] = arr[j];
    			k++;
    			j++;
    		}			
    	}
    	while (l <= mid) {
        
    		str[k] = arr[l];
    		k++;
    		l++;
    	}
    	while (j <= right) {
        
    		str[k] = arr[j];
    		k++;
    		j++;
    	}
    	for (int i = 0;j <k;i++){
        
    		arr[left] = str[i];
    		left++;
    	}
    	}
    }

## 快速排序 ##

快速排序：

1.  选定pivot中心轴（这里的pivot一开始选择是数组第一个元素）
2.  将大于pivot的数字放在pivot的右边
3.  将小于pivot的数字放在pivot的左边
4.  分别左右子序重复前三步操作

public static void main(String[] args) {
        
    	int[] arr = {
        -9,78,0,23,-567,70};
    	quicksort(arr,0,arr.length-1);
    }
    public static void quicksort(int[] arr, int left,int right){
        
    	if (left > right) return;
    	int l = left;
    	int r = right;
    	int pivot = arr[l];
    	while (l < r) {
        
    		while (l < r && arr[r] >= pivot){
        
    			r--;
    		}
    		if (l < r) {
        
    			arr[l] = arr[r];
    		}
    		while (l < r && arr[l] <= pivot){
        
    			l++;
    		}
    		if (l < r){
        
    			arr[r] = arr[l];
    		}
    		if (l >= r){
        
    			arr[l] = pivot;	
    		}
    	}
    	quicksort(arr,left,r-1);
    	quicksort(arr,r+1,right);
    }

[fd7c285a5b674ba0a33dc94e716c65fe.png]: /images/20220828/d0b9abb60b5d497daa98f527a0fcf0cf.png