笔者埋坑后面再来分析总结
1. 插入排序
直接插入排序：O(n^2)
代码语言：javascript复制public static int[] insertSort(int[] arr){
int i,j,temp;
for(i = 1; i < arr.length; i ){
temp = arr[i];
for(j = i; j > 0 && arr[j-1] > temp; j--){
arr[j] = arr[j-1];
}
arr[j] = temp;
}
return arr;
}二分插入排序：O(n^2)
代码语言：javascript复制public static int[] binaryInsertSort(int[] arr){
int i,j,low,high,mid,temp;
for(i = 1; i < arr.length; i ){
temp = arr[i];
low = 0;
high = i - 1;
while(low <= high){ //最后一个也要比较，比完就知道具体位置了
mid = (low high) / 2;
if(temp < arr[mid]){
high = mid - 1;
}else{
low = mid 1;
}
}
for(j = i; j > high 1; j--){
arr[j] = arr[j-1];
}
arr[high 1] = temp;
}
return arr;
}希尔排序：O(nlog n)
代码语言：javascript复制public static int[] shellSort(int[] arr){
int i,j,d,temp;
for(d = arr.length/2; d > 0; d /= 2){
for(i = d; i < arr.length; i ){
temp = arr[i];
for(j = i; j > 0 && arr[j-d] > temp; j -=d){
arr[j] = arr[j-d];
}
arr[j] = temp;
}
}
return arr;
}2. 交换排序
冒泡排序：O(n^2)
代码语言：javascript复制public static int[] bubbleSort(int[] arr){
int i,j,temp;
for(i = 0; i < arr.length - 1; i ){
for(j = 0; j < arr.length - 1 - i; j ){
if(arr[j] > arr[j 1]){
temp = arr[i 1];
arr[i 1] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}快速排序：O(nlog2 n)
代码语言：javascript复制public static int partition(int[] arr,int i,int j){
int temp = arr[i]; //基准
while(i < j){
while(i < j && temp <= arr[j]){
j--;
}
arr[i] = arr[j];
while(i < j && arr[i] < temp ){
i ;
}
arr[j] = arr[i];
}
arr[i] = temp;
return i;
}
public static void quickSort(int[] arr,int i,int j){
int mid;
if(i < j){
mid = partition(arr,i,j);
quickSort(arr, i, mid-1);
quickSort(arr, mid 1, j);
}
}3. 选择排序
简单选择排序：O(n^2)
代码语言：javascript复制public static void SimpleSelectSort(int[] arr){
int i,j,index,temp;
for(i = 0; i < arr.length-1; i ){
index = i;
for(j = i 1; j < arr.length; j ){
if(arr[index] > arr[j]){
index = j;
}
}
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}堆排序：O(nlog2 n)
代码语言：javascript复制public static void sift(int[] arr,int low,int high){
int i = low; //父结点
int j = i * 2; //左子结点
int temp = arr[i]; //临时保存根结点
while(j <= high){
if(j < high && arr[j] < arr[j 1]){
j ; //指向右子结点
}
if(temp < arr[j]){
arr[i] = arr[j]; //较大子节点放入根节点
i = j;
j = i * 2;
}else{
break; //默认左右子树是大根堆，若不用交换，当前结点的下面都是大根堆
}
}
arr[i] = temp; //最后筛选完成才将根节点与最后交换的结点互换
}
public static void heapSort(int[] arr){
//建立初始堆
int i,temp;
int length = arr.length-1;
for(i = length/2; i >= 0; i--){
sift(arr,i,length);
}
// 走 n-1躺
for(i = length; i >= 1; i--){
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp; //交换arr[1],arr[i]
sift(arr,0,i-1);
}
}4. 归并排序
二路查找：O(nlog2 n)
代码语言：javascript复制public static void merge(int[] arr,int left,int mid,int right){
int[] leftArr = new int[mid - left];
int[] rightArr = new int[right - mid 1];
for(int i = left; i < mid; i ){
leftArr[i - left] = arr[i];
}
for(int i = mid; i <= right; i ){
rightArr[i - mid] = arr[i];
}
int i = 0, j = 0;
int index = left;
while(i < leftArr.length && j < rightArr.length){
if(leftArr[i] < rightArr[j]){
arr[index] = leftArr[i];
i ;
index ;
}else{
arr[index] = rightArr[j];
j ;
index ;
}
}
while(i < leftArr.length){
arr[index] = leftArr[i];
i ;
index ;
}
while(j < rightArr.length){
arr[index] = rightArr[j];
j ;
index ;
}
}
public static void mergeSort(int[] arr, int left, int right){
if(left < right){
int mid = (left right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid 1, right);
merge(arr, left, mid 1, right);
}
}5. 基数排序(桶排序，非计数排序)
代码语言：javascript复制// 返回最大值
private static int findMax(int[] arr){
int temp = arr[0];
for(int value : arr){
if(temp < value){
temp = value;
}
}
return temp;
}
public static void radixSort(int[] arr){
int max = findMax(arr);
// 比较次数由最大值的位数决定
for(int i = 1; max / i > 0; i *= 10){
int[][] buckets = new int[arr.length][10];
// 将每一个值根据当前比较的位数放入桶中
for(int j = 0; j < arr.length; j ){
int num = (arr[j] / i) % 10;
buckets[j][num] = arr[j];
}
int k = 0;
for(int m = 0; m < 10; m ){
for(int n = 0; n < arr.length; n ){
if(buckets[n][m] != 0){
arr[k ] = buckets[n][m];
}
}
}
}
}
