排序算法
直接插入排序
基本思想
在要排序的一組數(shù)中魁袜，假設(shè)前面(n-1) [n>=2]個數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的座咆。如此反復(fù)循環(huán)，直到全部排好順序仓洼。
特點
穩(wěn)定性： 穩(wěn)定
平均時間復(fù)雜度： O(n^2)
空間復(fù)雜度： O(1)
實例
代碼
public static void insetSort(int[] arr) {
int len = arr.length;
//默認第一個元素有序介陶，從第二個元素開始比較
for (int j = 1; j < len; j++) {
int temp = arr[j];
int i = j - 1;
//依次比較找到插入位置
while (i >= 0 && arr[i] > temp) {
arr[i + 1] = arr[i];
i--;
}
arr[i+1] = temp;
}
}
Shell排序
基本思想
先將要排序的一組數(shù)按某個增量d（n/2,n為要排序數(shù)的個數(shù)）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序色建，然后再用一個較小的增量（d/2）對它進行分組哺呜，在每組中再進行直接插入排序。當增量減到1時箕戳，進行直接插入排序后某残，排序完成。
特點
穩(wěn)定性： 不穩(wěn)定
平均時間復(fù)雜度： O(n^1.3)
空間復(fù)雜度： O(1)
實例
代碼
public static void shellSort(int[] arr) {
int length = arr.length;
int increment = length;
while (true) {
//增量
increment = increment / 2;
//分組處理
for (int i = 0; i < increment; i++) {
//按照直接插入算法處理
for (int j = i+increment; j + increment < length; j += increment) {
int temp = arr[j];
int K = j - increment;
while (K >= 0 && arr[K] > temp) {
arr[K + increment] = arr[K];
K-=increment;
}
arr[K+increment] = temp;
}
}
//增量為1是退出
if (increment == 1) {
break;
}
}
}
簡單選擇排序
基本思想
基本思想：在要排序的一組數(shù)中陵吸，選出最小的一個數(shù)與第一個位置的數(shù)交換玻墅；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止壮虫。
特點
穩(wěn)定性： 不穩(wěn)定
平均時間復(fù)雜度： O(n^2)
空間復(fù)雜度： O(1)
實例
代碼
public static void selectSort(int[] arr) {
int len = arr.length;
int index = 0;
for (int i = 0; i < len; i++) {
int temp = arr[i];
//查找最大值
for (int j = i + 1; j < len; j++) {
if (temp < arr[j]) {
temp = arr[j];
index = j;
}
}
//交換位置
if (arr[i] != temp) {
SortUtils.swap(arr, i, index);
}
}
}
冒泡排序
基本思想
在要排序的一組數(shù)中澳厢，對當前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉剩拢，較小的往上冒线得。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換裸扶。
特點
穩(wěn)定性： 穩(wěn)定
平均時間復(fù)雜度： O(n^2)
空間復(fù)雜度： O(1)
實例
代碼
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len ; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
}
}
}
}
快速排序
基本思想
選擇一個基準元素,通常選擇第一個元素或者最后一個元素,通過一趟掃描框都，將待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分。
特點
穩(wěn)定性： 不穩(wěn)定
平均時間復(fù)雜度： O(nlgn)
空間復(fù)雜度： O(nlgn)
實例
代碼
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int middle = getMiddle(arr, low, high); //將list數(shù)組進行一分為二
quickSort(arr, low, middle - 1); //對低字表進行遞歸排序
quickSort(arr, middle + 1, high); //對高字表進行遞歸排序
}
}
public static int getMiddle(int[] arr, int low, int high) {
int tmp = arr[low]; //數(shù)組的第一個作為中軸
while (low < high) {
while (low < high && arr[high] > tmp) {
high--;
}
arr[low] = arr[high]; //比中軸小的記錄移到低端
while (low < high && arr[low] < tmp) {
low++;
}
arr[high] = arr[low]; //比中軸大的記錄移到高端
}
arr[low] = tmp; //中軸記錄到尾
return low; //返回中軸的位置
}
歸并排序
基本思想
歸并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表呵晨，即把待排序序列分為若干個子序列魏保，每個子序列是有序的。然后再把有序子序列合并為整體有序序列摸屠。
特點
穩(wěn)定性： 穩(wěn)定
平均時間復(fù)雜度： O(nlgn)
空間復(fù)雜度： O(n)
實例
代碼
//遞歸劃分
public static void mergeSort(int[] data, int left, int right) {
if(left<right){
//找出中間索引
int center=(left+right)/2;
//對左邊數(shù)組進行遞歸
mergeSort(data,left,center);
//對右邊數(shù)組進行遞歸
mergeSort(data,center+1,right);
//合并
merge(data,left,center,right);
}
}
//合并有序數(shù)組
public static void merge(int[] data, int left, int center, int right) {
int [] tmpArr=new int[data.length];
int mid=center+1;
//third記錄中間數(shù)組的索引
int third=left;
int tmp=left;
while(left<=center&&mid<=right){
//從兩個數(shù)組中取出最小的放入中間數(shù)組
if(data[left]<=data[mid]){
tmpArr[third++]=data[left++];
}else{
tmpArr[third++]=data[mid++];
}
}
//剩余部分依次放入中間數(shù)組
while(mid<=right){
tmpArr[third++]=data[mid++];
}
while(left<=center){
tmpArr[third++]=data[left++];
}
//將中間數(shù)組中的內(nèi)容復(fù)制回原數(shù)組
while(tmp<=right){
data[tmp]=tmpArr[tmp++];
}
System.out.println(Arrays.toString(data));
}
