您好,登錄后才能下訂單哦!
一般排序通常認(rèn)為是升序。
穩(wěn)定性:兩個(gè)相等的數(shù)據(jù)若在排序前后的相對(duì)位置不發(fā)生改變,則稱該算法是具備穩(wěn)定性的算法。
一:插入排序
原理: 將數(shù)組分為有序區(qū)間和無序區(qū)間,每次用無需區(qū)間的
第一個(gè)數(shù)與有序區(qū)間進(jìn)行比較。
時(shí)間復(fù)雜度:O(n*n),空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
代碼如下:
public static void insertSort0(int[] array) {
for (int i = 1; i < array.length; i++) {
// 有序區(qū)間 [0, i)
// 無序區(qū)間 [i, array.length)
int key = array[i];
int j;
for (j = i - 1; j >= 0 && array[j] > key; j--) {
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
二:希爾排序
原理:分組插排,每分隔gap個(gè)大小從數(shù)組中取一個(gè)數(shù),進(jìn)而將數(shù)組分成了若干 個(gè)組,重復(fù)此操作,直到gap=1;
時(shí)間復(fù)雜度:O(n)~O(n*n),空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
代碼如下:
public static void shellSort(int[] array){
int gap=array.length;
while(true){
gap=(gap/3)+1;//or gap=gap/2
insertSortWithGap(array,gap);
if(gap==1){
break;
}
}
}
private static void inserSortWithGap(int[] array,int gap){
for(int i=gap;i<array.length;i++){
int key=array[i];
int j;
for(j=i-gap;j>=0&&array[j]>key;j-=gap){
array[j+gap]=array[j];
}
array[j+gap]=key;
}
}
三:選擇排序
1.單向選擇排序
原理:每次從無序區(qū)間選出最大(或者最小)的數(shù)存放在無序區(qū)間的最后(最 前),直到所有的待排序數(shù)據(jù)排序完。
時(shí)間復(fù)雜度:O(n^2),空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
public static void selsctSort1(int[] array){
//每次選最小的放在無序區(qū)間的前面
for(int i=0;i<array.length-1;i++){//需要排序的次數(shù)
//有序:[0,i)
//無序:[i,array.length)
int minIndex=i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
swap(array,mindex,i);
}
}
public static void selsctSort2(int[] array){
//每次選最大的放在無序區(qū)間的后面
for(int i=0;i<=array.length-1;i++){
//無序:[0,array.length-i)
//有序:[array.length-i,array.length)
int maxIndex=0;
for(int j=1;j<array.length-i;j++){
if(array[j]>array[max]){
max=j;
}
}
int t=array[max];
array[max]=array[array.length-i-1];
array[array.length-i-1]=t;
}
2.雙向排序比較
原理:每一次從無序區(qū)間選出最小 + 最大的元素,存放在無序區(qū)間的最前和最后,直到全部待排序的數(shù)據(jù)元素排完 。
時(shí)間復(fù)雜度:O(n^2),空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
代碼如下:
public static void selectSort3(int[] array){
int low=0;
int high=array.length-1;
//[low,high]表示整個(gè)無序區(qū)間
while(low<=high){
int min=low;
int high=low;
for(int i=low+1;i<=max;i++){
if (array[i] < array[min]) {
min = i;
}
if (array[i] > array[max]) {
max = i;
}
swap(array, min, low);
if (max == low) {
max = min;
}
swap(array, max, high);
}
private void swap(int[] array, int i, int j) {
int t = array[i]; array[i] = array[j]; array[j] = t;
}
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。