搞了这么久，终于把几种常用的排序算法搞清楚了
时间复杂度为O(n ^ 2)的三个
直接插入排序，选择排序，冒泡排序
时间复杂度为O(N * logN)的排序算法
快速排序，归并排序，希尔排序，堆排序
归并排序空间复杂度为O（n）
其他空间复杂度均为O(1)
直接插入排序
1 import com.gxf.util.Util; 2 3 /** 4 * 直接插入排序 5 * @author GXF 6 * 7 */ 8 public class InsertSort { 9 10 public static void main(String[] args) {11 int array[] = {32, 1, 34, 54, 5, 6};12 13 Util.showInArray(array);14 15 InsertSort insertSort = new InsertSort();16 insertSort.insertSort(array);17 18 Util.showInArray(array);19 }20 21 public void insertSort(int array[]){22 if(array == null || array.length == 0)23 return;24 25 for(int i = 1; i < array.length; i++){26 int temp = array[i];27 int j = i;28 while(j >= 1 && array[j - 1] > temp)29 {30 array[j] = array[j - 1];31 j--;32 }//while33 array[j] = temp;34 }//for35 }36 37 38 } 选择排序
1 import com.gxf.util.Util; 2 3 /** 4 * 直接选择排序 5 * @author GXF 6 * 7 */ 8 public class SelectSort { 9 10 public static void main(String[] args) {11 SelectSort selectSort = new SelectSort();12 int array[] = {32, 1, 34, 54, 5, 6};13 Util.showInArray(array);14 selectSort.selectSort(array);15 Util.showInArray(array);16 17 }18 19 /**20 * 直接选择排序21 * @param array22 */23 public void selectSort(int array[]){24 for(int i = 0; i < array.length; i++){25 int min = i;26 for(int j = i + 1; j < array.length; j++){27 if(array[j] < array[min])28 min = j;29 }//for30 if(min != i){31 int temp = array[i];32 array[i] = array[min];33 array[min] = temp;34 }//if35 }//for36 }37 } 冒泡排序
1 import com.gxf.util.Util; 2 3 /** 4 * 直接选择排序 5 * @author GXF 6 * 7 */ 8 public class SelectSort { 9 10 public static void main(String[] args) {11 SelectSort selectSort = new SelectSort();12 int array[] = {32, 1, 34, 54, 5, 6};13 Util.showInArray(array);14 selectSort.selectSort(array);15 Util.showInArray(array);16 17 }18 19 /**20 * 直接选择排序21 * @param array22 */23 public void selectSort(int array[]){24 for(int i = 0; i < array.length; i++){25 int min = i;26 for(int j = i + 1; j < array.length; j++){27 if(array[j] < array[min])28 min = j;29 }//for30 if(min != i){31 int temp = array[i];32 array[i] = array[min];33 array[min] = temp;34 }//if35 }//for36 }37 } --------------------------------------------------我是分割线---------------------------------------------------
快速排序
1 /** 2 * 快速排序 3 * 先是一次划分 4 * @author GXF 5 * 6 */ 7 public class QuickSort { 8 9 10 public static void main(String[] args) {11 QuickSort quickSort = new QuickSort();12 int array[] = {32, 1, 34, 54, 5, 6};13 Util.showInArray(array);14 quickSort.quickSort(array, 0, array.length - 1);15 Util.showInArray(array);16 17 }18 19 /**20 * 快速排序21 * @param array22 * @param start23 * @param end24 */25 public void quickSort(int array[], int start, int end){26 if(start < end){27 int index = partion(array, start, end);28 quickSort(array, start, index - 1);29 quickSort(array, index + 1, end);30 }31 }32 33 /**34 * 一次划分35 * @param array36 * @param start37 * @param end38 * @return39 */40 public int partion(int array[], int start, int end){41 int key = array[start];42 while(start < end){43 while(start < end && array[end] > key) //从后面开始扫描44 end--;45 array[start] = array[end];46 while(start < end && array[start] < key)47 start++;48 array[end] = array[start];49 }//while50 array[start] = key;51 52 return start;53 }54 55 } 归并排序
1 import com.gxf.util.Util; 2 3 /** 4 * 归并排序 5 * 归并：递归 + 合并 6 * 时间复杂度O（n * logn） 7 * 空间复杂度O(N) 8 * @author GXF 9 *10 */11 public class MergeSort {12 13 14 public static void main(String[] args) {15 int array[] = {32, 1, 34, 54, 5, 6};16 MergeSort mergeSort = new MergeSort();17 Util.showInArray(array);18 mergeSort.mergeSort(array);19 Util.showInArray(array);20 21 }22 23 24 public void mergeSort(int array[]){25 if(array == null || array.length == 0)26 return;27 mergeSort(array, 0, array.length - 1, new int[array.length]);28 }29 30 /**31 * 归并排序32 * 升序排列33 * @param array34 * @param start35 * @param last36 * @param temp37 */38 private void mergeSort(int array[], int start, int last, int temp[]){39 if(start < last){40 int middle = (start + last) / 2;41 mergeSort(array, start, middle, temp);42 mergeSort(array, middle + 1, last, temp);43 merge(array, start, middle, last, temp);44 }45 }46 47 /**48 * 合并两个数组49 * @param array50 * @param start51 * @param middle52 * @param last53 * @param temp54 */55 public void merge(int array[], int start, int middle, int last, int temp[]){56 int first = start;57 int second = middle + 1;58 int k = 0;59 60 while(first <= middle && second <= last){61 if(array[first] < array[second])62 temp[k++] = array[first++];63 else64 temp[k++] = array[second++];65 }//while66 67 while(first <= middle)68 temp[k++] = array[first++];69 while(second <= last)70 temp[k++] = array[second++];71 for(int i = 0; i < k; i++)72 array[start + i] = temp[i];73 }74 75 } 希尔排序
1 import com.gxf.util.Util; 2 3 /** 4 * 希尔排序 5 * 时间复杂度O（n * logn） 6 * 空间复杂度O（1） 7 * @author GXF 8 * 9 */10 public class ShellSort {11 12 13 public static void main(String[] args) {14 int array[] = {32, 1, 34, 54, 5, 6};15 ShellSort shellSort = new ShellSort();16 Util.showInArray(array);17 shellSort.shellSort(array);18 Util.showInArray(array);19 20 }21 22 /**23 * 这段代码整理的确实漂亮24 * @param array25 */26 public void shellSort(int array[]){27 if(array == null || array.length == 0)28 return;29 for(int gap = array.length / 2; gap > 0; gap /= 2){30 for(int i = gap; i < array.length; i++){31 for(int j = i; j >= gap && array[j] < array[j - gap]; j -= gap)32 swap(array, j, j - gap);33 }34 }35 }36 37 private void swap(int array[], int i, int j){38 int temp = array[i];39 array[i] = array[j];40 array[j] = temp;41 }42 43 } 堆排序
1 import com.gxf.util.Util; 2 3 /** 4 * 堆排序 5 * 时间复杂度O（n * logn） 6 * 空间复杂度O（1） 7 * @author GXF 8 * 9 */10 public class HeapSort {11 12 public static void main(String[] args) {13 int array[] = {32, 1, 34, 54, 5, 6};14 HeapSort heapSort = new HeapSort();15 Util.showInArray(array);16 heapSort.heapSort(array);17 Util.showInArray(array);18 19 }20 21 /**22 * 堆排序23 * 升序排列24 * 先建立一个大根堆25 * 用数组最后一个元素和第一个元素交换，调整大根堆26 * @param array27 */28 public void heapSort(int array[]){29 //建堆30 for(int i = array.length / 2 - 1; i >= 0; i--){31 maxHeapFixDown(array, i, array.length);32 }33 //调整堆34 for(int i = array.length - 1; i >= 0; i--){35 swap(array, 0, i);36 maxHeapFixDown(array, 0, i);37 }38 }39 40 /**41 * 对大根堆中，i节点进行向下调整42 * @param array43 * @param i44 */45 private void maxHeapFixDown(int array[], int i, int n){46 int temp = array[i];47 int j = 2 * i + 1;48 while(j < n && i < n){49 //选出子节点中最大的50 if(j + 1 < n && array[j] < array[j + 1])51 j = j + 1;52 if(array[j] < temp)53 break;54 //子节点中最大的向上移动55 array[i] = array[j];56 i = j;57 j = 2 * i + 1;58 }//while59 array[i] = temp;60 }61 62 private void swap(int array[], int i, int j){63 int temp = array[i];64 array[i] = array[j];65 array[j] = temp;66 }67 }