排序算法
冒泡排序：
public static void bubbleSort(int [] arr){
boolean flag=false;
for (int i =0; i < arr.length; i++) {
for (int j =1; j < arr.length-i; j++) {
if(arr[i]>arr[j]){
swap(arr[i],arr[j]);
flag=true;
}
}
if(flag==false){
return;
}
}
}
归并排序
publicstaticint[] MergeSort(int[] array) {
if(array.length < 2)return array;
intmid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
publicstaticint[] merge(int[] left,int[] right) {
int[] result =newint[left.length + right.length];
for(intindex = 0, i = 0, j = 0; index < result.length; index++) {
if(i >= left.length)
result[index] = right[j++];
elseif(j >= right.length)
result[index] = left[i++];
elseif(left[i] > right[j])
result[index] = right[j++];
else result[index] = left[i++];
}
return result;
}
快速排序
public static void sort(int data[],int start,int end) {
if (end - start <=0) {
return;
}
int smallindex = start;
for (int i = start +1; i < end; i++) {
if (data[i] < data[start]) {
smallindex++;
swap(data,i,smallindex);
}
}
swap(data,start,smallindex);
sort(data, start, smallindex -1);
sort(data, smallindex+1, end);
}
public void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
堆排序：保证每一次移动一个节点，该节点的作为树根的树，都是最小堆（理解while循环）
public static void headSort(int[] list) {
for (int i = (list.length) /2 -1; i >=0; i--) {
headAdjust(list, list.length, i);
}
for (int i = list.length -1; i >=1; i--) {
swap(list,0,i);
headAdjust(list, i,0);
}
}
private static void headAdjust(int[] list,int len,int parent) {
//k是父亲临时位置，temp是父节点的临时值
int k = parent, temp = list[parent], child =2 * k +1;
while (child < len) {
if (child +1 < len) {
if (list[child] < list[child +1]) {
child = child +1;
}
}
if (list[child] > temp) {
list[k] = list[child];
k = child;
child =2 * k +1;
}else {
break;
}
}
list[k] = temp;
}
