缺失：希爾排序帝簇、堆排序
優(yōu)化：快速排序
待補(bǔ)充狀態(tài)
導(dǎo)讀
?簡單算法：冒泡排序O(n2)徘郭、簡單選擇排序O(n2)靠益、直接插入排序O(n2)
?改進(jìn)算法：歸并排序O(nlogn)、快速排序(冒泡排序優(yōu)化)O(nlogn)残揉、計數(shù)排序胧后、基數(shù)排序或桶子法、希爾排序(插入排序優(yōu)化)O(n3/2)抱环、堆排序(選擇排序優(yōu)化)O(nlogn)
1. 排序問題
1.0 直接使用Arrays.sort(數(shù)組名)方法進(jìn)行排序
int[] d={123,456,19};
Arrays.sort(d);
但有時需要我們使用算法實(shí)現(xiàn)壳快，則基本排序常用方法如下：
public static void main(String[] args) {
int[] num = {230,229,8,0,26,25,224,223};
bubbleSort(num); //1.1 冒泡排序
selectSort(num); //1.2 選擇排序
insertSort(num); //1.3 插入排序
mergeSort(num); //1.4 歸并排序
quickSort(num); //1.5 快速排序
Arrays.toString(num); //打印數(shù)組
}
1.1 冒泡排序：BubbleSort
冒泡排序主要是比較相鄰的兩位數(shù)字，取較大值與下一位比較镇草，直至到最高位眶痰，完成一輪；第二輪比較至次高位梯啤，以此類推
public static void bubbleSort(int[] num) {
for (int i = num.length - 1竖伯，temp=0; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (num[j] > num[j + 1]) {
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
}
1.2 選擇排序：SelectSort
選擇排序，首先選出最小值放在第一位因宇；第二輪選出次小值放在第二位七婴，以此類推
public static void selectSort(int[]num) {
for (int i = 0,temp=0; i < num.length-1; i++) {
for(int j=i+1;j<num.length;j++){
if(num[i]>num[j]){
temp = num[j];
num[j] = num[i];
num[i] = temp;
}
}
}
}
1.3 插入排序：InsertSort
先選定第二個數(shù)為標(biāo)記數(shù)，當(dāng)且僅當(dāng)?shù)谝粋€數(shù)大于等于標(biāo)記數(shù)時羽嫡，才循環(huán)，交換標(biāo)記數(shù)與第一個數(shù)的位置肩袍，此時設(shè)置第一個數(shù)為標(biāo)記數(shù)杭棵；以此類推
public static void insertSort(int[]num) {
for (int i = 1,temp=0,j=0; i < num.length; i++) {
temp=num[i];
j=i;
while(j>0&&num[j-1]>temp){
num[j]=num[j-1];
num[j-1]=temp;
j--;
}
}
}
1.4 歸并排序：MergeSort
分治策略；序列一分為二氛赐，然后對子序列進(jìn)行遞歸排序魂爪，最后合并有序子序列
public static void mergeSort(int[]num){
sort(num,0,num.length-1);
}
public static void sort(int[]num,int left,int right){
if(left<right){
int center=(left+right)>>1;
sort(num,left,center);
sort(num,center+1,right);
merge(num,left,center,right);
}
}
public static void merge(int[]num,int left,int center,int right){
//創(chuàng)建臨時數(shù)組，暫存數(shù)據(jù)
int[] tmpArr=new int[num.length];
int third=left;
int temp=left;
int mid=center+1;
//對兩個子序列中取出較小的放入臨時數(shù)組艰管，直至某子序列全部放完
while(left<=center&&mid<=right){
if(num[left]<=num[mid]){
tmpArr[third++]=num[left++];
}else{
tmpArr[third++]=num[mid++];
}
}
//此處兩個while只能運(yùn)行一個
while(mid<=right){
tmpArr[third++]=num[mid++];
}
while(left<=center){
tmpArr[third++]=num[left++];
}
//此處把數(shù)據(jù)從臨時數(shù)組中復(fù)制回原數(shù)組
while(temp<=right){
num[temp]=tmpArr[temp++];
}
}
1.5 快速排序
以數(shù)組中的某位隨機(jī)數(shù)為比較值key滓侍，從右、左分別向中間逼近牲芋，一次排序把小于比較值key的放在左邊撩笆，大于比較值key的放在右邊，然后再對兩邊子序列分別進(jìn)行排序缸浦，以此類推
1.5.1 基本快速排序：QuickSort
以數(shù)組中的首數(shù)或尾數(shù)為比較值key：
public static void quickSort(int[]num){
if(num==null||num.length<=0){
System.out.println("error data");
return;
}
sort(num,0,num.length-1);
}
public static void sort(int[] num,int left,int right){
if(left<right){
int center=getMiddle(num,left,right);
sort(num,left,center-1);
sort(num,center+1,right);
}
}
public static int getMiddle(int[] num,int left,int right){
int tmp=num[left];
while(left<right){
//兩個while分別從右夕冲、左向中間逼近
while(left<right&&tmp<=num[right]){
right--;
}
if(left<right){
num[left]=num[right];
left++;
}
while(left<right&&num[left]<=tmp){
left++;
}
if(left<right){
num[right]=num[left];
right--;
}
}
num[left]=tmp;
return left;
}
1.5.2 隨機(jī)化快速排序：RandomQuickSort
隨機(jī)設(shè)定比較值key：
public static void randomQuickSort(int[] num) {
if (num == null || num.length <= 0) {
System.out.println("error data");
return;
}
sort(num, 0, num.length - 1);
}
public static void sort(int[] num, int left, int right) {
if (left < right) {
int middle = randomNum(num, left, right); //內(nèi)容有變動
sort(num, left, middle - 1);
sort(num, middle + 1, right);
}
}
//新增方法
public static int randomNum(int[] num, int left, int right) {
//獲取left與right中間的任意隨機(jī)值
int random = (int) (left + Math.random() * (right - left));
int temp = num[left];
num[left] = num[random];
num[random] = temp;
return getMiddle(num, left, right);
}
public static int getMiddle(int[] num, int left, int right) {
int tmp = num[left];
while (left < right) {
while (left < right && tmp <= num[right]) {
right--;
}
if (left < right) {
num[left] = num[right];
left++;
}
while (left < right && num[left] <= tmp) {
left++;
}
if (left < right) {
num[right] = num[left];
right--;
}
}
num[left] = tmp;
return left;
}
1.6 計數(shù)排序：CountSort
統(tǒng)計數(shù)組中的各數(shù)出現(xiàn)的次數(shù)，然后再安排先后順序一一打印出來
public static void countSort(int[] num) {
if(num==null||num.length<=0){
System.out.println("error data");
return;
}
int max=0,min=0;
for(int i=0;i<=num.length-1;i++){
if(num[i]<min){
min=num[i];
}
if(num[i]>max){
max=num[i];
}
}
int [] newNum=new int[max-min+1];
for(int i=0;i<=num.length-1;i++){
newNum[num[i]-min]++;
}
int count=0;
for(int i=0;i<newNum.length;i++){
while(newNum[i]>0){
num[count++]=min+i;
newNum[i]--;
}
}
}
1.7 基數(shù)排序或桶子法：RadixSort 或 BucketSort
1.7.1 LSD法
最低位優(yōu)先(Least Significant Digit first)法：先獲取最高位數(shù)裂逐，然后從低向高依次排序歹鱼，即個、十卜高、百弥姻、千位···
import java.util.List; //導(dǎo)入List集合包
import java.util.ArrayList; //導(dǎo)入ArrayList包
public static void radixSort(int[] num) {
if (num == null || num.length <= 0) {
System.out.println("error data");
return;
}
sort(num);
}
public static void sort(int[] num) {
// 計算數(shù)組中最大數(shù)k的位數(shù)time
int k = num[0], time = 1;
for (int i = 0; i < num.length; i++) {
k = k < num[i] ? num[i] : k;
}
while (k / 10 != 0) {
time++;
k /= 10;
}
// 創(chuàng)建0-9個ArrayList存放數(shù)據(jù)
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
// 進(jìn)行time次分配
for (int i = 0; i < time; i++) {
for (int j = 0; j < num.length; j++) {
int x = num[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(num[j]);
queue.set(x, queue2);
}
// printqueue(queue); //打印list數(shù)組
int count = 0;
// 收集隊列元素
for (int m = 0; m < 10; m++) {
for (int t = 0; t < queue.get(m).size(); t++) {
num[count++] = (int) queue.get(m).get(t);
}
queue.get(m).clear();
}
}
}
1.7.2 MSD法
最高位優(yōu)先(Most Significant Digit first)法：先獲取最高位數(shù)南片，然后依次從高位到低位進(jìn)行排序；即···千庭敦、百疼进、十、個位
暫時缺失
## 排序的穩(wěn)定性與不變性
#### 不變性
在算法運(yùn)行時保持不變的條件
#### 穩(wěn)定性
如果具有相同關(guān)鍵字的數(shù)據(jù)項螺捐，經(jīng)過排序它們的順序保持不變颠悬，這樣的排序就是穩(wěn)定的