1、插入排序
public static int[] insertSort(int[] array) {
int length = array.length;
int j = 0;
for(int i = 1; i < length; i++) {
int temp = array[i];
for(j = i; j > 0; j--) {
if(temp < array[j-1]) {
array[j] = array[j-1];
}else {
break;
}
}
array[j] = temp;
}
return array;
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
swap(arr,j,j-1);
j--;
}
}
}
public static void swap(int []arr,int a,int b){
arr[a] = arr[a]+arr[b];
arr[b] = arr[a]-arr[b];
arr[a] = arr[a]-arr[b];
}
2、冒泡排序
public static int[] bubbleSort(int[] array) {
int length = array.length;
for(int i = 0; i < length; i++ ) {
for(int j = 1; j < length - i; j++) {
if(array[j] < array[j -1]) {
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
return array;
}
3、快速排序
public static void quickSort2(int[] a,int low,int high) {
if(low >= high) {
return ;
}
int i = low;
int j = high;
int temp = a[low];
while(i < j) {
//先从右边开始，找到第一个比temp小的数，注意是a[j] >= temp
while(i < j && a[j] >= temp) j--;
while(i < j && a[i] <= temp) i++;
if(i < j) {
//交换位置
int temp1 = a[i];
a[i] = a[j];
a[j] = temp1;
}
}
//基准数归位
a[low] = a[i];
a[i] = temp;
quickSort2(a,low,i-1);
quickSort2(a,j+1,high);
}
4、堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
- 堆是一个完全二叉树的结构，分为大顶堆和小顶堆。大顶堆即是节点的值大于左右节点的值。
- 堆排序的思路是：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
5、归并排序
public static void sort(int[] arr, int L, int R) {
if(L == R) {
return;
}
int mid = L + ((R - L) >> 1);
sort(arr, L, mid);
sort(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R) {
int[] temp = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while(p1 <= mid && p2 <= R) {
temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while(p1 <= mid) {
temp[i++] = arr[p1++];
}
while(p2 <= R) {
temp[i++] = arr[p2++];
}
// 把最终的排序的结果复制给原数组
for(i = 0; i < temp.length; i++) {
arr[L + i] = temp[i];
}
}
6、希尔排序
public int[] shellSort(int[] arr){
for (int d =arr.length/2 ; d > 0 ; d = d/2) {
for (int x = 0; x < d; x++) {
for (int i = x+d; i < arr.length; i= i+d) {
int temp=arr[i];
int j;
for (j=i-d;j>= 0 &&arr[j]>temp;j=j-d) {
arr[j+d]=arr[j];
}
arr[j+d]=temp;
}
}
}
return arr;
}
、、、
https://www.cnblogs.com/chengxiao/p/6194356.html
https://www.jianshu.com/p/33cffa1ce613
https://mp.weixin.qq.com/s/885uGVhlffWAxjgIEW-TiA
