java——快排、冒泡、希尔、归并
2024-10-07 15:36:47
直接贴代码
快排:
public class Test {
private static void sort(int[] nums){
if(nums == null || nums.length == 0){
return;
}
quickSort(nums, 0, nums.length-1);
} private static void quickSort(int[] nums, int start, int end) {
int low = start;
int high = end;
int temp = nums[start];
while(start<end){
while (start<end && nums[end]>=temp){
end--;
}
swap(nums, start, end);
while(start<end && nums[start]<=temp){
start++;
}
swap(nums, start, end);
}
if(start-1>low) {
quickSort(nums, low, start - 1);
}
if(high>start+1) {
quickSort(nums, start + 1, high);
}
} private static void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
} public static void main(String [] args){
int[] nums = {49,22,34, 6,22,19,3,19};
sort(nums);
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]+“ ”);
} }
}
冒泡:
private static void bubbleSort(int[] num){
for(int i = 0 ; i < num.length ; i ++) {
for(int j = 0 ; j < num.length - i - 1 ; j ++){
if(num[j]>num[j+1]){
swap(num, j , j+1);
}
}
}
}
改进冒泡:
public void bubbleSort(int arr[]) {
boolean didSwap;
for(int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j]) {
swap(arr, j, j + 1);
didSwap = true;
}
}
if(didSwap == false)
return;
}
}
改进后的冒泡排序最佳情况下时间复杂度为O(n)
希尔排序:
private static void shellSort(int[] nums){
for(int d = nums.length/2 ; d > 0 ; d = d / 2){
for(int i = d ; i < nums.length ; i ++){
for(int j = i; j>=d; j = j-d){
if (nums[j] < nums[j - d]) {
swap(nums, j - d, j);
}else{
break;
}
}
}
}
}
归并排序:
private static void mergeSort(int[] nums, int low, int high){
if(low>=high){
return;
}
int mid = (low+high)/2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums,low, mid, high);
} private static void merge(int[] nums, int low, int mid, int high){
int[] temp = new int[high-low+1];
int i = low;
int j = mid+1;
int k = 0;
while(i<=mid&&j<=high){
if(nums[i]<nums[j]){
temp[k++] = nums[i++];
}else{
temp[k++] = nums[j++];
}
}
while(i<=mid){
temp[k++] = nums[i++];
}
while(j<=high){
temp[k++] = nums[j++];
}
for(int p = 0 ; p < temp.length ; p++){
nums[low+p] = temp[p];
}
}
最新文章
- struts2中错误There is no Action mapped for namespace [/] and action name [] associated with context path
- 使用Fiddler搭建手机调试环境(我做得项目是调试微信的公众号)
- mysql dba系统学习(6)二进制日志binlog之二
- Apache Tomcat相应插件版本
- 判断文件是否存在(exist)
- codevs2622数字序列( 连续子序列最大和O(n)算法)
- SetCapture ReleaseCapture
- 【解决方案】客户端请求数据较大时,nginx返回数据被截断
- Azure Automation (6) 执行Azure SQL Job
- Google Guava的5个鲜为人知的特性
- 重写override
- SQL强化练习(面试与学习必备)
- 我的SSH框架实例(附源码)
- 使用JWT的RSA256加密做为用户认证, 测试性能
- git clone 指定分支 拉代码
- [游记] HEOI2018酱油记
- PSQL_标准API和Interface基本的用法和比较(概念)
- 基于redis的分布式缓存disgear开源到github上了
- 测试php中的curl是否可使用
- 使用imp命令和exp命令对oracle数据库进行导入导出操作