欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-10 21:13:17
10 大排序算法只有以下 4 种是不稳定的:快(快速排序);些(希尔排序);选(选择排序);堆(堆排序)。快速排序最差时间复杂度每次选取的基准都是最大(或最小)的元素,导致每次只划分出了一个分区,需要进行n-1次划分才能结束递归,时间复杂度为O(n^2)最优时间复杂度每次选取的基准都是中位数,这样每次都均匀的划分出两个分区,只需要logn次划分就能结束递归,时间复杂度为O(nlogn)...

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