常见的10种排序算法总结
【摘要】 1：冒泡排序稳定时间复杂度：最好：O(n)、最坏：O（n^2^）、平均：O（n^2^）空间复杂度：O（1）void bubbleSort(int[]arr,int n){ for(int i=0;i<n-1;i++){ boolean flag= false; for(int j=0;j<n-i-1;j++){ if(arr[j]>arr[j+1]){ swap(arr,j,...
1：冒泡排序
稳定
时间复杂度：
最好：O(n)、最坏：O（n^2^）、平均：O（n^2^）
空间复杂度：
O（1）
void bubbleSort(int[]arr,int n){
for(int i=0;i<n-1;i++){
boolean flag= false;
for(int j=0;j<n-i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
flag= true;
}
}
if(flag == false)
break;
}
}
2：选择排序
不稳定
时间复杂度：
最好：O（n^2^）、最坏：O（n^2^）、平均：O（n^2^）
空间复杂度：
O（1）
void SelectSort(int[]arr,int n){
for(int i=0;i<n-1;i++){
//前面已经排好序，选择后面最小的一个进行交换
for(int j=i+1;j<n;j++){
if(arr[j]<arr[i]){
swap(arr,i,j);
}
}
}
}
3：插入排序
稳定
时间复杂度：
最好：O（n）、最坏：O（n^2^）、平均：O（n^2^）
空间复杂度：
O（1）
void InsertSort(int[]arr,int n){
for(int i=0;i<n-1;i++){
//前面已经排好序，后面的一个往前插入
for(int j=i+1;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr,j-1,j);
}else{
break;
}
}
}
}
4：希尔排序
不稳定
时间复杂度：
最好：O（n）、最坏：O（n^2^）、平均：O（n^1.3^）
空间复杂度：
O（1）
void InsertSort(int[]arr,int n){
//改进版的插入排序
//相比于插入排序，其可以越过几个数进行比较，这样可以减少比较次数
//最好的时候：就是有序的，其实这样的话比插入排序复杂了些，但是量级一样（我猜的）
int d = n>>1;
while(d>=1){
for(itn i=d;i<n;i++){
//前面的已经排好序，后面的往前插入
for(int j=i;j>=d;j=j-d){
if(arr[j]<arr[j-d]){
swap(arr,j,j-d);
}
}
}
d = d>>1;
}
}
5：快速排序
不稳定
时间复杂度：
最好：O（nlogn）、最坏：O（n^2^）、平均：O（nlogn）
空间复杂度：
O（logn）
void FastSort(int[]nums,int i,int j){
if(i<j){
int mid= partitionTwo(nums,i,j);
FastSort(nums,i,mid-1);
FastSort(nums,mid+1,j);
}
}
//大量和pivot重复的，可以平均分割
int partitionTwo(int[]nums,int i,int j){
//基准点随机
int ran =(int) (i + (j-i)*Math.random());
swap(nums,ran,i);
int start = i;
int pivot = nums[i];
i = i+1;
///相当于把等于key的值均分到两边
while(i<=j){
while(i<=j&&nums[j]>pivot){
j--;
}
while(i<=j&&nums[i]<pivot){
i++;
}
if(i>j){
break;
}
swap(nums,i,j);
i++;
j--;
}
swap(nums,start,j);
return j;
}
//单路：有一个弊端，就是如果有重复的，造成不平衡
int partition(int[]nums,int i,int j){
//基准点随机
int ran =(int) (i + (j-i)*Math.random());
swap(nums,ran,i);
//思路：将小于首节点的全部放在一边
int l = i;//一个指针
int pivot = nums[i];
//迭代方法
for(int k=l+1;k<=j;k++){
if(nums[k]<=pivot){
swap(nums,l+1,k);
l++;
}
}
swap(nums,l,i);
return l;
}
// //三路快排
// //可以解决解决含有大量重复值（和pivot相同的）,直接略过
// void ThridFastSort(int[]nums,int start,int end){
// if(start<end){
// int[]pivotpos = ThridpartitionThrid(nums,start,end);
// ThridFastSort(nums,start,pivotpos[0]);
// ThridFastSort(nums,pivotpos[1],end);
// }
// }
// int[] ThridpartitionThrid(int[]nums,int start,int end){
// //随机快速排序，防止已经排序好
// int random = (int)(Math.random() * (end - start + 1)) + start;
// swap(nums,random,start);
// int pivot = nums[start];
// int i = start + 1;
// int gt = end + 1;
// int lt = start;
// while(i<gt){
// if(nums[i]<pivot){
// swap(nums,i,lt+1);
// i++;
// lt++;
// }else if(nums[i]>pivot){
// swap(nums,i,gt-1);
// gt--;
// }else{
// i++;
// }
// }
// swap(nums,start,lt);
// return new int[]{lt,gt};
// }
6：归并排序
稳定
时间复杂度：
最好：O（nlogn）、最坏：O（nlogn）、平均：O（nlogn）
空间复杂度：
O（n）
void Merge(int[]nums,int start,int end,int[]temp){
if(start<end){
int mid = start + (end-start)/2;
Merge(nums,start,mid,temp);
Merge(nums,mid+1,end,temp);
MergeSort(nums,start,mid,end,temp);
}
}
void MergeSort(int[]nums,int start,int mid,int end,int[]temp){
int start2 = mid+1;
int k =0;
int l = start;
while(start<=mid && start2<=end){
if(nums[start]<=nums[start2]){
temp[k++] = nums[start++];
}else{
temp[k++] = nums[start2++];
}
}
while(start<=mid){
temp[k++] = nums[start++];
}
while(start2<=end){
temp[k++] = nums[start2++];
}
for(int i=0;i<k;i++){
nums[l++] = temp[i];
}
}
7：堆排序
不稳定
时间复杂度：O（ nlogn）
空间复杂度：O（1）
void heapSort(int[]nums,int n){
//创建堆--最大堆
//从最后一个非叶子节点
for(int i=n/2-1;i>=0;i--){
adjust(nums,n,i);
}
for(int i=n-1;i>0;i--){
swap(nums,0,i);
adjust(nums,i,0);
}
}
void adjust(int[]nums,int n,int index){
int l = index*2+1;
int r = index*2+2;
int maxIndex = index;
if(l<n && nums[maxIndex]<nums[l]){
maxIndex = l;
}
if(r<n && nums[maxIndex]<nums[r]){
maxIndex = r;
}
if(maxIndex!=index){
swap(nums,maxIndex,index);
adjust(nums,n,maxIndex);
}
}
8：计数排序
稳定
时间复杂度：O（ n + max - min）
空间复杂度：O（max - min）
int min = nums[0];
int max = nums[0];
for(int i=1;i<n;i++){
if(nums[i]<min){
min = nums[i];
}
if(nums[i]>max){
max = nums[i];
}
}
int[]temp = new int[max-min+1];
for(int i=0;i<n;i++){
temp[nums[i]-min]++;
}
int k = 0;
for(int i=0;i<max-min+1;i++){
for(int j=0;j<temp[i];j++){
nums[k++] = i + min;
}
}
9：桶排序
稳定性：每个桶的排序算法
时间复杂度：m * O(k * logk)=m * O((n / m)*log(n / m))=O(nlog(n / m)) ==O(n) (n>>m)
空间复杂度：O（n+m）----自己取m，桶的个数
void bucketSort(int[]nums,int n){
// //桶的个数
// // 计算最大值与最小值
// int max = Integer.MIN_VALUE;
// int min = Integer.MAX_VALUE;
// for(int i = 0; i < n; i++){
// max = Math.max(max, nums[i]);
// min = Math.min(min, nums[i]);
// }
// // 计算桶的数量
// int bucketNum = (max - min) / n + 1;
// //每个桶放入不同范围内的值
// ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
// for(int i = 0; i < bucketNum; i++){
// bucketArr.add(new ArrayList<Integer>());
// }
// for(int i=0;i<n;i++){
// int x = (nums[i] - min)/n;
// bucketArr.get(x).add(nums[i]);
// }
// for(int i = 0;i<bucketNum;i++){
// Collections.sort(bucketArr.get(i));
// }
// int k = 0;
// for(int i=0;i<bucketNum;i++){
// for(int j =0;j<bucketArr.get(i).size();j++){
// nums[k++] = bucketArr.get(i).get(j);
// }
// }
10：基数排序
稳定
时间复杂度：O（n * k) k为桶的个数，ru:10
空间复杂度： O(n + k)
void radixSort(int[]nums,int n){
// int max = Integer.MIN_VALUE;
// for(int i =0;i<n;i++){
// max = Math.max(max,nums[i]);
// }
// int sum = 0;
// while(max!=0){
// max = max/10;
// sum++;
// }
// int[][] bucket=new int[10][n];
// int[]order = new int[10];
// int x = 1;
// while(x<=Math.pow(10,sum-1)){
// //放入桶中
// for(int i =0;i<n;i++){
// int val = nums[i];
// val = (val/x)%10;
// bucket[val][order[val]] = nums[i] ;
// order[val]++;
// }
// //全部拿出来
// int k = 0;
// for(int i=0;i<10;i++){
// if(order[i]!=0){
// for(int j=0;j<order[i];j++){
// nums[k++] = bucket[i][j];
// }
// }
// order[i]=0;
// }
// x*=10;
// }
// }
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）