常见排序算法-冒泡排序、选择排序 、插入排序 、快速排序、 归并排序 、堆排序
常见排序算法-冒泡排序、选择排序 、插入排序 、快速排序、 归并排序 、堆排序
才疏学浅的木子
发布于 2022-11-20 16:50:13
发布于 2022-11-20 16:50:13
???个人主页： 才疏学浅的木子 ??♂? 本人也在学习阶段如若发现问题，请告知非常感谢 ??♂? ? 本文来自专栏： 算法 ? 算法类型：排序算法 ?
排序算法
冒泡排序
在这里插入图片描述
平均时间复杂度： o(n^2) 最好时间： o(n) 最坏时间： o(n^2) 空间复杂度： o(1) 是否稳定： 稳定
简单的冒泡排序
public int[] bubbleSort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
for(int i = 0;i < len;i++){
for(int j = 0;j < len-i-1;j++){
if(nums[j] > nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}冒泡排序的优化
设置标志位
设置一个标志位来标识这次遍历是否进行过交换 如果没有进行过交换则表示数组已经有序，直接退出
public int[] binarySort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
for(int i = 0;i < len-1;i++){
boolean isSort = true; //是否有序
for(int j = 0;j < len-i-1;j++){
if(nums[j] > nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
isSort = false;
}
}
if(isSort) break;
}
return nums;
}设置结束位置
比如初始数组为[4,3,2,1,5,6] 经过第一次排序后数组变为[3,2,1,4,5,6] 如果按照普通冒泡排序下次需要遍历的下标范围为[0,4] 但是[3,4]是已经有序的，所以可以减少比较，保存上次交换的结束位置
public int[] bubbleSort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
int max_index = len-1;
int index = max_index;
for(int i = 0;i < len-1;i++){
boolean isSort = true; //是否有序
for(int j = 0;j < index;j++){
if(nums[j] > nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
isSort = false;
max_index=j;
}
}
if(isSort) break;
index = max_index;
}
return nums;
}双向冒泡排序
与设置结束位置类似，这个是也设置了起始位置 使得在left之前的都是已经排好序的
public int[] bubbleSort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
int left = 0;
int right = len-1;
int tleft = 0,tright = 0;
while(left < right){
boolean isSort = true;
for(int i = left;i < right;i++){
if(nums[i+1] < nums[i]){
int temp = nums[i];
nums[i] = nums[i+1];
nums[i+1] = temp;
isSort = false;
tright = i;
}
}
if(isSort)break;
right = tright;
isSort = true;
for(int i = right;i > left;i--){
if(nums[i] < nums[i-1]){
int temp = nums[i];
nums[i] = nums[i-1];
nums[i-1] = temp;
isSort = false;
tleft = i;
}
}
if(isSort)break;
left = tleft;
}
return nums;
}选择排序
在这里插入图片描述
平均时间复杂度： o(n^2) 最好时间： o(n^2) 最坏时间： o(n^2) 空间复杂度： o(1) 是否稳定： 不稳定
选择排序
public int[] selectSort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
for(int i = 0;i < len;i++){
int minIndex = i;
for(int j = i;j < len;j++){
if(nums[j] < nums[minIndex]){
minIndex = j;
}
}
int t = nums[minIndex];
nums[minIndex] = nums[i];
nums[i] = t;
}
return nums;
}插入排序
在这里插入图片描述
平均时间复杂度： o(n^2) 最好时间： o(n) 最坏时间： o(n^2) 空间复杂度： o(1) 是否稳定： 稳定
插入排序
public int[] insertSort(int [] nums){
int len = nums.length;
if(len <= 1) return nums;
for(int i = 1;i < len;i++){
int cur = nums[i];
int preIndex = i - 1;
while(preIndex >= 0 && nums[preIndex] > cur){
nums[preIndex+1] = nums[preIndex];
preIndex--;
}
nums[preIndex+1] = cur;
}
return nums;
}快速排序
在这里插入图片描述
平均时间复杂度： o(nlogn) 最好时间： o(nlogn) 最坏时间： o(n^2) 空间复杂度： o(logn) 是否稳定： 不稳定
快速排序
public void quickSort(int [] nums,int left,int right){
if(left >= right) return;
int l = left - 1;
int r = right + 1;
int t = nums[left];
while(l < r){
do l++;while(nums[l] < t);
do r--;while(nums[r] > t);
if(l < r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
}
quickSort(nums,left,r);
quickSort(nums,r+1,right);
}归并排序
在这里插入图片描述
平均时间复杂度： o(nlogn) 最好时间： o(nlogn) 最坏时间： o(nlogn) 空间复杂度： o(n) 是否稳定： 稳定
public void mergeSort(int [] nums,int left,int right){
if(left >= right) return;
int mid = left + right >> 1;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//需要合并 [left,mid] [mid+1,right]
int []temp = new int[right-left+1];
int l = left,r = mid+1,k = 0;
while(l <= mid && r <= right){
if(nums[l] < nums[r]) temp[k++] = nums[l++];
else temp[k++] = nums[r++];
}
while(l <= mid) temp[k++] = nums[l++];
while(r <= right) temp[k++] = nums[r++];
for(int i = right;i >= left;i--){
nums[i] = temp[--k];
}
}堆排序
在这里插入图片描述
平均时间复杂度： o(nlogn) 最好时间： o(nlogn) 最坏时间： o(nlogn) 空间复杂度： o(1) 是否稳定： 不稳定
public void heapSort(int [] nums){
int len = nums.length;
if(len <= 1) return;
//构造大根堆
for(int i = (len-1)/2; i>=0 ;i--){
heap(nums,i,len);
}
//将根弄到最后
for(int i = len-1;i >=0; i--){
int t = nums[0];
nums[0] = nums[i];
nums[i] = t;
heap(nums,0,i);
}
}
//子树构建大顶堆
public void heap(int[] nums,int index,int size){
int max = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if(left < size && nums[left] > nums[max]) max = left;
if(right < size && nums[right] > nums[max]) max = right;
if(max != index){
int t = nums[index];
nums[index] = nums[max];
nums[max] = t;
heap(nums,max,size);
}
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录