1.归并排序
package sort;
import java.util.Arrays;
public class MergeSort {
/**
* 归并排序 简介：将两个（或两个以上）有序表合并成一个有序表，即把待排序的序列分成若干个子序列，每个序列是有序的。
* 然后再把有序的子序列合并成整体有序的序列。 时间复杂度为o(nlogn) 稳定排序方式
*
* @param nums 待排序数组
* @return 输出有数数组
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
sort(nums, low, mid);
// 右边
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
public 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++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
// 归并排序的实现
public static void main(String[] args) {
int[] nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
MergeSort.sort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
}
2.冒泡排序
package sort;
import java.util.Arrays;
//简单冒泡排序
//冒泡排序重复地走过要排序的数列，一次比较两个元素，若顺序错误就把他们交换，直到没有需要交换
public class BubbleSort1 {
//比较相邻的元素，若第一个比第二个大，就交换，对每一对相邻元素做同样工作，从开始第一对到结尾最后一对。
//针对所有的元素重复以上的步骤，除了最后一个，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
/*public static void bubble(int[] nums){int temp;int size = nums.length;for(int i=0;inums[j]){
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
}*///严格上说这段代码不是标准的冒泡排序，因为它不满足“两两比较”，应该是最简单的交换排序，效率非常低
/*public static void bubble(int[] nums){int temp;int size = nums.length;for(int i=0;ii;j--){
if(nums[j-1]>nums[j]){
temp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = temp;
}
}
}
}*///这样的冒泡排序还可以优化，如果待排序的序列是{2，1，3，4，5，6，7，8，9}，第一和第二的关键字交换后就没必要再交换了。
public static void bubble(int[] nums){int temp;int size = nums.length;int flag = 1;for(int i=0;ii;j--){
if(nums[j-1]>nums[j]){
temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
flag = 1;
}
}
}
}//对于{2，1，3，4，5，6，7，8，9}，当i=2时已经对9和8，8和7..做了比较，没有交换的数据，说明序列已有序，不需要增加循环，可以增加一个标记变量flag实现改进
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums ={7,6,4,9,5,2,0,1,3,8};
bubble(nums);
System.out.println(Arrays.toString(nums));
}
}
网友评论