排序代码
直接插入排序
public static void insertSort(int[] array){
for(int i = 0;i<array.length-1;i++){
int current = array[i+1];
int index = i;
while (index>=0&¤t<array[index]){
array[index+1]=array[index];
index--;
}
array[index+1] = current;
}
}
shell排序
public static void shellSort(int[] array){
int gap = array.length/2;
while (gap > 0) {
for(int i = 0;i<array.length-gap;i++){
int current = array[i+gap];
int index = i;
while (index>=0&¤t<array[index]){
array[index+gap] = array[index];
index-=gap;
}
array[index+gap]=current;
}
gap=gap/2;
}
}
直接选择排序
public static void selectionSort(int[] array){
//需要一个选择比较循环,其中需要一个current记录目前搜索到的最小值
int current;
for(int i = 0;i<array.length-1;i++){
current = i;
for (int j = current+1;j<array.length;j++){
if(array[j]<array[current]){
current = j;
}
}
if (current != i) {
int tmp = array[current];
array[current] = array[i];
array[i] = tmp;
}
}
}
堆排序
public static void heapSort(int[] array){
//大顶推排序注意在于, 大顶堆只能知道最大的数,而不知道第二大的数,但第二大的数一定在左右子树之中
//所以将根节点与交换之后,只进行一次heapify就可以找到新的最大值,并且第二大又在其子树中
//首先进行一次制作大顶堆,从最后一个非叶子结点开始,从后往前制作
//建堆复杂度为n,每次建堆后减少一个,所以最后复杂度为nlogn
int size = array.length;
for (int i = size/2-1;i>=0;i--){
heapify(array,size,i);
}
//现在此数组符合大顶堆,所以其根节点就为最大的值,将根节点即第一个值与最后一个值交换,再对剩下的数
//以第一个值为根节点实现一次大顶堆工具,循环~
for(int i = size-1;i>0;i--){
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
heapify(array,i,0);
}
}
//制作大顶堆工具,一个大顶堆单元
public static void heapify(int[] array,int size,int root){
int max = root;
int left = root*2+1;
int right = root*2+2;
if(left<size&&array[left]>array[max]){
max = left;
}
if(right<size&&array[right]>array[max]){
max = right;
}
if (max != root) {
int tmp = array[max];
array[max] = array[root];
array[root] = tmp;
heapify(array,size,max);
}
}
冒泡排序
public static void bubbleSort(int[] array){
for(int i = 0;i<array.length-1;i++){
for(int j = 0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
快速排序
//挖坑填数+分治法
public static void quickSort(int[] array){
sort(array,0,array.length-1);
}
public static void sort(int[] array,int low,int high){
if (low < high) {
int mid = part(array, low, high);
sort(array,low,mid-1);
sort(array,mid+1,high);
}
}
public static int part(int[] array,int low,int high){
//基准值
int i = low;
int j = high;
int mid = array[low];
while (i < j) {
while (i < j&&array[j] > mid) {
j--;
}
//别忘了这里i需要向后移
//填坑
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j&&array[i] < mid) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] = mid;
return i;
}
归并排序
public static void mergeSort(int[] array){
int low = 0;
int high = array.length-1;
mergeSort(array,low,high);
}
public static void mergeSort(int[] array,int low,int high){
int mid = (low+high)/2;
if (low < high) {
//分块
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
//归并
merge(array,low,mid,high);
}
}
//归并排序中将两个块进行排序工具类
public static void merge(int[] array,int low,int mid,int high){
int start1 = low;
int start2 = mid+1;
int[] tmp = new int[high-low+1];
int k = 0;
while (start1 <= mid && start2 <= high) {
tmp[k++]=array[start1]<array[start2]?array[start1++]:array[start2++];
}
while (start1 <= mid) {
tmp[k++] = array[start1++];
}
while (start2 <= high) {
tmp[k++] = array[start2++];
}
// 把新数组中的数覆盖nums数组
if (tmp.length >= 0) System.arraycopy(tmp, 0, array, low, tmp.length);
}
基数排序
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 获取最高位数
*/
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];//建桶
for (int j = 0; j < arr.length; j++) {
//从个位开始
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}