资料来源：
https://blog.csdn.net/yushiyi6453/article/details/76407640
https://www.cnblogs.com/suiyue-/p/6561051.html
https://www.cnblogs.com/developerY/p/3166462.html
gitHub 相关源码路径：
https://github.com/mackzheng/BriefBook/blob/master/Arithmetic/src/main/java/com/avl/arithmetic/Sort/ArraySort.java
排序分为内排序和外排序。
内排序：
1.插入排序：直接插入排序，折半插入排序，希尔排序。
2.选择排序：简单选择排序，堆排序。
3.交换排序：冒泡排序，快速排序。
4.归并排序
5.桶排序：基数排序，计数排序
外排序
6.多路归并
7.败者树
稳定性：
能够保证相同数据的前后位置不发生变化。
稳 定：冒插归计基
不稳定：选快堆希
时间复杂度：
O(n^2) 冒选插
O(nlogn) 归快堆希
O(n+k) 计数
O(N*M) 基数
image.png
==========================
1.冒泡排序：
public static void bubbleSort(int[] numbers)
{
if (numbers == null) return;
int temp = 0;
int size = numbers.length;
for (int i = 0; i < size -1; i++) {
for (int j = 0; j < size - 1 -i ; j++) {
if(numbers[j]>numbers[j+1])
{
temp = numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]= temp;
}
}
}
}
==========================
2.选择排序：
// 每次找出最小的那个数
public static int[] selectSort(int[] nums)
{
if(nums == null) return null;
for(int i=0;i<nums.length;i++)
{
int k = i;
for(int j=k+1; j<nums.length; j++)
{
if(nums[j]<nums[k])
{
k = j;
}
}
if(i!=k)
{
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
return nums;
}
//这种算法是找出一个数，找出比这个数小的输交换。不太好理解的选择排序。
public static void selectSort(int[] numbers)
{
int length = numbers.length;
for (int i=0; i<length ;i++)
{
int temp = numbers[i];
int index = i;
for (int j=i+1;j<length;j++)
{
if(numbers[j] < temp)
{
temp = numbers[j];
index = j;
}
}
numbers[index] = numbers[i];
numbers[i] = temp;
}
}
==========================
3.插入排序：
public static void insertSort(int[] datas)
{
int length = datas.length;
int insertNum;
for (int i=1;i<length;i++)
{
insertNum = datas[i];
int j = i-1;
while(j>=0 && datas[j]>insertNum)
{
datas[j+1] = datas[j];
j--;
}
datas[j+1] = insertNum;
}
}
==========================
4.快速排序：
public static void quickSort(int[] numbers, int start, int end)
{
if(numbers==null) return;
if(start<end)
{
int baseNum = numbers[start];
int midNum;
int i = start;
int j = end;
while(i<=j)
{
while(i < end && numbers[i]<baseNum)
{
i++;
}
while (j>start && numbers[j]>baseNum)
{
j--;
}
if(i<=j)
{
midNum = numbers[i];
numbers[i] = numbers[j];
numbers[j] = midNum;
i++;
j--;
}
if(j>start)
{
quickSort(numbers,start,j);
}
if(i<end)
{
quickSort(numbers,i,end);
}
}
}
}
==========================
5.归并排序：
public static void mergeSort(int[] datas,int low,int hight)
{
int mid = (low+hight)/2;
if(low<hight)
{
mergeSort(datas,low,mid);
mergeSort(datas,mid+1,hight);
merge(datas,low,mid,hight);
}
}
private static void merge(int[] datas,int low,int mid,int hight)
{
int[] temp = new int[hight-low+1];
int i=low;
int j=mid+1;
int k =0;
while (i<=mid && j<=hight)
{
if(datas[i]<datas[j])
{
temp[k++]=datas[i++];
}else
{
temp[k++]=datas[j++];
}
}
while (i<=mid)
{
temp[k++] = datas[i++];
}
while (j<=hight)
{
temp[k++]=datas[j++];
}
for (int m=0;m<temp.length;m++)
{
datas[low+m] = temp[m];
}
}
==========================
6.堆排序：
public static void heapSort(int[] datas)
{
createHeap(datas);
for (int i=datas.length-1;i>1;--i)
{
int temp =datas[1];
datas[1] = datas[i];
datas[i] = temp;
HeapAdjust(datas,1,i-1);
}
}
private static void createHeap(int[] datas)
{
int length = datas.length-1;
for (int i=length/2;i>0;i--)
{
HeapAdjust(datas,i,length);
}
}
private static void HeapAdjust(int[] datas,int cur,int last)
{
int temp = datas[cur];
for (int j=2*cur; j<=last; j *=2)
{
if(j<last && datas[j]< datas[j+1])
{
++j;
}
if (temp >= datas[j])
{
break;
}
datas[cur] = datas[j];
cur = j;
}
datas[cur] = temp;
}
==========================
7.希尔排序
private static void sheelSort(int[] datas)
{
if(datas == null) return;
int len = datas.length;
while (len!=0)
{
len = len/2;
for (int i=0;i<len;i++)
{
for (int j=i+len;j<datas.length;j+=len)
{
int k=j-len;
int temp = datas[j];
while (k>=0&& temp <datas[k])
{
datas[k+len] = datas[k];
k-=len;
}
datas[k+len]=temp;
}
}
}
}
==========================
8.基数排序
public static void baseSort(int[] datas)
{
int max = datas[0];
for (int i=1;i<datas.length;i++)
{
if(datas[i]>max)
{
max = datas[i];
}
}
int time = 0;
while(max>0)
{
max/=10;
time++;
}
List<ArrayList<Integer>> queue = new ArrayList<>();
for (int i=0;i<10;i++)
{
ArrayList<Integer> queueItem = new ArrayList<>();
queue.add(queueItem);
}
for (int i=0;i<time;i++)
{
for (int j=0;j<datas.length;j++)
{
int x= (int) (datas[j] % Math.pow(10,i+1)/(int) Math.pow(10,i));
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(datas[j]);
queue.set(x,queue2);
}
int count =0;
for (int k=0;k<10;k++)
{
while (queue.get(k).size()>0)
{
ArrayList<Integer> queue3 = queue.get(k);
datas[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
==========================
9.计数排序 https://www.cnblogs.com/developerY/p/3166462.html
private static int[] countSort(int[] datas,int k)
{
int[] C = new int[k+1];
int length = datas.length;
int sum = 0;
int[] B = new int[length];
for (int i=0;i<length;i++)
{
C[datas[i]]+=1;
}
for (int i=0;i<k+1;i++)
{
sum+=C[i];
C[i] = sum;
}
for (int i=length-1;i>=0;i--)
{
B[C[datas[i]]-1] = datas[i];
C[datas[i]]--;
}
return B;
}
==========================
测试代码：
public static void main(String[] args) {
int[] a = {3, 4, 8, 2, 1, 6};
//1.冒泡排序
//bubbleSort(a);
//print(a);
//2.快速排序
//quickSort(a,0,a.length-1);
//print(a);
//3.选择排序
//selectSort(a);
//print(a);
//4.插入排序
//insertSort(a);
//print(a);
//5.归并排序
//mergeSort(a,0,a.length-1);
//print(a);
//6.堆排序
//int[] b = {0,3, 4, 8, 2, 1, 6};
//heapSort(b);
//print(b);
//7.希尔排序
//sheelSort(a);
//print(a);
//8.基数排序
//int[] c = {3, 4, 8, 2, 1, 6,100,98,66,1000};
//baseSort(c);
//print(c);
//9.计数排序
int[] d = countSort(a, 10);
print(d);
}
private static void print(int[] a)
{
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
网友评论