荐 最普通的---》排序算法
程序员文章站
2022-07-10 21:13:17
10 大排序算法只有以下 4 种是不稳定的:快(快速排序);些(希尔排序);选(选择排序);堆(堆排序)。快速排序最差时间复杂度每次选取的基准都是最大(或最小)的元素,导致每次只划分出了一个分区,需要进行n-1次划分才能结束递归,时间复杂度为O(n^2)最优时间复杂度每次选取的基准都是中位数,这样每次都均匀的划分出两个分区,只需要logn次划分就能结束递归,时间复杂度为O(nlogn)...
10 大排序算法只有以下 4 种是不稳定的:
快(快速排序);
些(希尔排序);
选(选择排序);
堆(堆排序)。
快速排序
|
|
|
|
|
|
|
|
|
|
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;
}
}
选择排序
数据移动最少的
选择排序,设定开头元素为最小元素,循环遍历查找是否有新最小的元素可替换,前部有序区域逐渐变大
|
|
|
|
|
|
|
|
|
|
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;
}
}
}
}
插入排序
适用:
- 数组每个元素距离它的最终位置都不远
- 一个有序大数组接一个小数组
- 数组中只有几个元素位置不正确
希尔排序是由插入排序进行优化
|
|
|
|
|
|
|
|
|
|
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;
}
}
}
希尔排序
希尔排序,也叫递减增量排序,是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
各个子数组都很短,排序之后子数组都是部分有序(符合插入排序高性能时条件)。希尔排序就是调用若干趟插入排序。
|
|
|
|
|
|
|
|
|
|
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
上一篇: CompletableFuture
下一篇: 【矩阵】面试题 01.07. 旋转矩阵