快排

private static void quickSort(int[] ret) {
????quick(ret,0,ret.length-1);
}
private static void quick(int[] ret, int left, int right) {
????if(left>=right) ????記一下這里是大于等于???

return;
????int pivot = partition(ret,left,right);
????quick(ret,left,pivot-1);
????quick(ret,pivot+1,right);
}
private static int partition(int[] ret, int left, int right) {
????int key = ret[left];
????int i = left;
????while(left<right){
????????while(left<right&&ret[right]>=key){
????????????right--;
????????}
????????while(left<right&&ret[left]<=key){
????????????left++;
????????}
????????swap(ret,left,right);
????}
????swap(ret,i,left);
????return left;
}
private static void swap(int[] ret, int left, int right) {
????int tmp = ret[left];
????ret[left] = ret[right];
????ret[right] = tmp;
}

歸并

????private static void mergeSort(int[] ret) {
????????merge(ret, 0, ret.length - 1);
????}
????private static void merge(int[] ret, int left, int right) {
????????if (left >= right)?記一下這里是大于等于
????????????return;
// 1. 根據中間點劃分區間
????????int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 先把左右區間排個序
????????merge(ret, left, mid);
????????merge(ret, mid + 1, right);
// 3. 合并兩個有序數組
????????int[] tmp = new int[ret.length];
????????int cur1 = left, cur2 = mid + 1, i = 0;
????????while (cur1 <= mid && cur2 <= right)
????????????tmp[i++] = ret[cur1] <= ret[cur2] ? ret[cur1++] : ret[cur2++];
// 處理沒有遍歷完的數組
????????while (cur1 <= mid)
????????????tmp[i++] = ret[cur1++];
????????while (cur2 <= right)
????????????tmp[i++] = ret[cur2++];
// 4. 還原
????????for (int j = left; j <= right; j++)
????????????ret[j] = tmp[j - left];
????}

}

堆排

private static void heapSort(int[] ?array) {
????for(int parent=(array.length-1-1)/2;parent>=0;parent--){
??????????siftDown(array,parent,array.length);
????}
????int end = array.length - 1;
????while(end>0){
????????swap(array,0,end);
????????siftDown(array,0,end);
????????end--;
????}
}

private static void swap(int[] array, int a, int b) {
????int tmp = array[a];
????array[a] = array[b];
????array[b] = tmp;
}

private static void siftDown(int[] array, int parent, int end) {
????int child = 2 * parent + 1;
????while(child<end){
????????if(child+1<end&&array[child+1]>array[child]){
????????????child++;
????????}
????????if(array[child]>array[parent]) {
????????????swap(array, child, parent);
????????????parent = child;
????????????child = 2 * parent + 1;
????????}else {
????????????break;
????????}
????}
}

選擇

private static void selectSort(int[] array) {
????for (int i = 0; i < array.length; i++) {
????????int minIndex = i;
????????for (int j = i+1; j < array.length; j++) {
????????????if(array[j]<array[minIndex]){
????????????????minIndex = j;
????????????}
????????}
????????swap(array,minIndex,i);
????}
}

冒泡

private static void bubbleSort(int[] array) {
????for (int i = 0; i < array.length-1; i++) {
????????boolean flag = false;
????????for (int j = 0; j < array.length-1-i; j++) {
????????????if(array[j]> array[j+1]){
????????????????swap(array,j,j+1);
????????????????flag = true;
????????????}
????????}
????????if(!flag)
?????????????return ;
????}
}

插入

private static void insertSort(int[] array) {
????for (int i = 1; i < array.length; i++) {
????????int tmp = array[i];
????????int j = i-1;
????????for (; j >=0; j--) {
????????????if(array[j]>tmp){
????????????????array[j+1] = array[j];
????????????}else{
????????????????break;
????????????}
????????}
???????array[j+1] = tmp;
????}
}

希爾(gap是幾，分成幾組)

private static void shellSort(int[] array){
????int gap = array.length;
????while(gap>1){

// ?gap必須寫在前面
?????????gap/=2;
?????????shell(array,gap);
????}
}

private static void shell(int[] array, int gap) {
????for (int i = gap; i < array.length; i++) {
????????int tmp = array[i];
????????int j = i-gap;
????????for (; j >=0; j-=gap) {
????????????if(array[j]>tmp){
????????????????array[j+gap] = array[j];
????????????}else{
????????????????break;
????????????}
????????}
????????array[j+gap] = tmp;
????}
}