冒泡排序
時(shí)間復(fù)雜度:n^2贼涩。
每一輪比較都從頭開(kāi)始,然后兩兩比較,如果左值比右值大,則交換位置,每一輪結(jié)束后,當(dāng)前輪"最后一個(gè)元素"必將是最大的.
public void bubbling(int[] arr, int length){
for(int i = 0; i < length-1; i++){
for(int j = 0; j< length -i -1; j++){
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
快速排序
時(shí)間復(fù)雜度:n*logN
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小抄腔,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序俱济,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列垢乙。
public static void quictSort(int[] sources,int start,int end){
if(start < end){
int tmp;
int i = start;
int j = end;
int value = sources[i];
while(i < j){
while(sources[j] > value && i<j){
j--;
}
//右邊找到了比key大的.
tmp = sources[i];
sources[i] = sources[j];
sources[j] = tmp;
while(sources[i] < value && i<j){
i++;
}
//左邊找到了比key大的值
tmp = sources[i];
sources[i] = sources[j];
sources[j] = tmp;
}
for (int x = 0; x < sources.length; x++) {
System.out.print(sources[x] + " ");
}
System.out.println();
quictSort(sources, start, j - 1);
quictSort(sources, j + 1, end);
}
}
插入排序
時(shí)間復(fù)雜度:n^2
把待排序的紀(jì)錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中氮兵,直到所有的紀(jì)錄插入完為止,得到一個(gè)新的有序序列
public void insertSort(int[] arr, int size){
for(int i=0; i < size-1; i++){
for(int j=i; j>0; j--){
if(arr[j] < arr[j-1]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
}
歸并排序
時(shí)間復(fù)雜度:n*logN 空間復(fù)雜度: n
分治法,將數(shù)組逐步拆分為"組",直到最小的"組",然后每個(gè)組內(nèi)排序,然后依次和相鄰的組"排序合并",其中"排序".其內(nèi)部排序非常簡(jiǎn)單.直接比較.
public static void mergeSort(int[] sources,int begin,int end){
if(begin < end){
int range = end - begin;
int mid = begin + range/2;
mergeSort(sources, begin, mid);//左段
mergeSort(sources, mid + 1, end);//右端
System.out.println(Arrays.toString(sources));
merge(sources, begin, mid, end);
}
}
private static void merge(int[] sources,int begin,int mid,int end){
int[] tmp = new int[end - begin + 1];
int b1 = begin;
int e1 = mid;
int b2 = mid+1;
int e2 = end;
int i=0;
for(;b1 <= e1 && b2 <= e2 ; i++){
//填充tmp數(shù)組,并依此在兩段數(shù)據(jù)區(qū)域中找到最小的
if(sources[b1] <= sources[b2]){
tmp[i] = sources[b1];
b1++;
}else{
tmp[i] = sources[b2];
b2++;
}
}
//到此為止,兩段數(shù)據(jù)區(qū)域,已經(jīng)至少一個(gè)被掃描完畢
if(b1 > e1){
//如果b1~e1掃描完畢,那么可能b2~e2還有剩余
for(int t = b2;t < e2 + 1; t++){
tmp[i] = sources[t];
i++;
}
}
if(b2 > e2){
//如果b2~e2掃描完畢,那么可能b1~e1還有剩余
for(int t = b1;t < e1 + 1; t++){
tmp[i] = sources[t];
i++;
}
}
//replace and fill:將tmp數(shù)組的數(shù)據(jù),替換到source中,begin~end
//因?yàn)榇藭r(shí)tmp中的數(shù)據(jù)是排序好的
i=0;
for(int t= begin;t <= end; t++){
sources[t] = tmp[i];
i++;
}
tmp = null;//
}