把我上學時候在csdn上的筆記搬過來了
簡單選擇排序
選擇排序要用到交換胳挎,在開始之前不妨說下數(shù)值交換的三種方法
臨時變量
public static void swap(int[] arr, int i, int j) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
加法
public static void swap(int[] arr, int i, int j) {
if (i != j) {
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
異或
public static void swap(int[] arr, int i, int j) {
if(i!=j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
簡單選擇排序思路很簡單署照,就是每次遍歷數(shù)組獲得最小值得位置,然后將最小值與數(shù)組中第一個值交換簇秒,然后從第二個值開始遍歷獲得最小值與第二個元素交換,以此類推。
public static void selectSort(int[] arr) {
int min;
for (int i = 0; i < arr.length; i++) {
min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, min, i);
}
}
最好最肺缕、壞時間復雜度都是O(n2)。內層for循環(huán)執(zhí)行次數(shù)依次為n-1授帕,n-2同木,n-3,……,1。加起來為n(n-1)/2 跛十。 該算法是不穩(wěn)定的泉手,很容易理解,由于交換的時候偶器,會改變兩個相等值得相對位置斩萌。
直接插入排序
將序列中的第一個元素作為一個有序序列缝裤,然后將剩下的n-1個元素按照關鍵字大小依次插入該有序序列,每插入一個元素后依然保持該序列有序颊郎,經過n-1趟排序后即成為有序序列憋飞。
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
int temp = arr[i];
while (j > 0 && temp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
算法必須進行n-1趟。最好情況下姆吭,每趟都比較一次榛做,時間復雜度為O(n);最壞情況下的時間復雜度為O(n2)内狸。 插入排序是穩(wěn)定的检眯,當然這與循環(huán)條件中”temp < arr[j - 1]”密切相關,如果改為”temp < =arr[j - 1]” 那么就不穩(wěn)定了昆淡。
冒泡排序
第一趟在數(shù)組(arr[0]-arr[n-1])中從前往后進行兩個相鄰元素的比較锰瘸,若后者小,則交換昂灵,比較n-1次避凝;第一趟排序結束,最大的元素到 arr[n-1] 中 眨补;下一趟排序在子數(shù)組arr[0]-arr[n-2]中進行管削;如果在某一趟排序中未交換元素,說明子序列已經有序撑螺,不需要再進行下一趟排序含思。
public static void bubbleSort(int[] arr) {
int i = arr.length - 1;
int last;//記錄某趟最后交換的位置,其后的元素都是有序的
while (i > 0) {
last=0;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
last= j;
}
}
i=last;
}
}
其中變量last主要是要記錄甘晤,某趟遍歷時最后一次交換的位置茸俭。在last之后的元素其實都已經在排序結果中正確的位置。后面再進行下一趟時安皱,只要從arr[0]到arr[last] 進行操作即可调鬓。最終當last=0時,就說明arr[0]之后的元素都已經在正確的位置了酌伊,那么只剩arr[0]肯定也是在正確的位置腾窝。
該算法最多進行n-1趟。冒泡排序在已排序的情況下是最好情況居砖,只用進行一趟虹脯,比較n-1次,時間復雜度為O(n) ; 最壞情況下要進行n-1趟奏候,第i每次比較n-i次循集,移動3(n-i)次,時間復雜度為O(n2); 冒泡排序是穩(wěn)定的排序算法蔗草,這當然也與算法中的判斷條件相關咒彤。
快速排序
快排簡略來說就是一種分治的思想疆柔。對一個數(shù)組,選定一個基準元素x镶柱,把數(shù)組劃分為兩個部分旷档,低端部分都比x小,高端元素都比x大歇拆,那么此時基準元素就在正確的位置了鞋屈。然后再分別都低端部分和高端部分,分別進行上面的步驟故觅,直到子數(shù)組中只有一個元素為止厂庇。
遞歸版
public static void quickSort(int[] arr) {
qSort(arr, 0, arr.length - 1);
}
private static void qSort(int[] arr, int left, int right) {
//如果分割元素角標p為子數(shù)組的邊界,那么分割后就只有低端序列或者高端序列输吏,此時判斷防止角標越界
if(left==right){
return;
}
int p = partition(arr, left, right);
qSort(arr, left, p - 1);
qSort(arr, p+1,right);
}
/**
* 把數(shù)組分為兩部分
*
* @param arr
* @param left
* 子數(shù)組最小角標
* @param right
* 子數(shù)組最大角標
* @return 返回分割元素的角標
*/
private static int partition(int[] arr, int left, int right) {
int base = arr[right];
int small=left-1;//用來記錄小于base的數(shù)字放到左邊第幾個位置
for(int i=left;i<right;i++){
if(arr[i]<base){
small++;
swap(arr,small,i);
}
}
small++;
swap(arr, small,right);
return small;
}
非遞歸版
public static void quickSort(int[] arr){
Deque<Integer> leftStack=new ArrayDeque<Integer>();
Deque<Integer> rightStack=new ArrayDeque<Integer>();
leftStack.addFirst(0);
rightStack.addFirst(arr.length-1);
while(leftStack.size()!=0){
Integer left = leftStack.removeFirst();
Integer right = rightStack.removeFirst();
int p = partition(arr, left, right);
if(p>left){
leftStack.addFirst(left);
rightStack.addFirst(p-1);
}
if(p<right){
leftStack.addFirst(p+1);
rightStack.addFirst(right);
}
}
}
上面partition函數(shù)中每次選擇子數(shù)組中第一個元素作為基準元素权旷,當然你也可以選擇其他的。
當初始數(shù)組有序(順序或逆序)時评也,快排效率最低炼杖,因為每次分割后有一個子數(shù)組是空灭返,時間復雜度是O(n2)盗迟;在平均情況下可以證明快排的時間復雜度是O(nlogn)。
在最壞的情況下空間復雜度是O(n),最好的情況下是O(logn)熙含。
我們可以看出無論是遞歸還是非遞歸罚缕,快排至少O(logn)的空間復雜度,這個是省不掉的怎静。
快排是不穩(wěn)定的邮弹。
歸并排序
把n個長度的數(shù)組看成是n個長度為1的數(shù)組,然后兩兩合并時排序蚓聘,得到n/2個長度為2的數(shù)組(可能包含一個1); 繼續(xù)兩兩合并排序腌乡,依次類推。
歸并排序算法的核心是合并夜牡,我具體來說一下合并的思路与纽。比如我們有數(shù)組A,B,此時我們要在合并時排序,需要一個臨時數(shù)組C塘装。用leftPosition急迂,rightPosition和tempPositon 分別來指示數(shù)組元素,它們的起始位置對應數(shù)組的始端。A[leftPostion]和B[rightPosition]中較小者被拷貝到C中tempPostion的位置蹦肴。相關的指示器加1僚碎。當A和B中有一個用完時,另一個數(shù)組中的剩余部分直接拷貝到C中阴幌。
代碼如下:
/**
* @param arr
* 數(shù)組
* @param tempArr
* 臨時數(shù)組勺阐,用于臨時存放合并后的結果
* @param leftPostion
* 第一個子數(shù)組的開始
* @param rightPosition
* 第二個字數(shù)組的開始位置
* @param rightEnd
* 第二個子數(shù)組的結束位置
*/
private static void merge(int[] arr, int[] tempArr, int leftPostion,
int rightPosition, int rightEnd) {
int leftEnd = rightPosition - 1;
int tempPositon = leftPostion;
int begin=leftPostion;
while (leftPostion <= leftEnd && rightPosition <= rightEnd) {
if(arr[leftPostion]<arr[rightPosition]){
tempArr[tempPositon++]=arr[leftPostion++];
}else {
tempArr[tempPositon++]=arr[rightPosition++];
}
}
while(leftPostion<=leftEnd){
tempArr[tempPositon++]=arr[leftPostion++];
}
while(rightPosition<=rightEnd){
tempArr[tempPositon++]=arr[rightPosition++];
}
//復制到原數(shù)組
for(int i=begin;i<=rightEnd;i++){
arr[i]=tempArr[i];
}
}
private static void mergeSort(int[] arr, int[] tempArr, int left, int right) {
if(left<right){//如果只有一個子數(shù)組只有一個元素就直接返回
int mid=(left+right)/2;
mergeSort(arr,tempArr,left,mid);
mergeSort(arr,tempArr,mid+1,right);
merge(arr, tempArr, left, mid+1, right);
}
}
public static void mergeSort(int[] arr) {
int[] tempArr=new int[arr.length];
mergeSort(arr,tempArr,0,arr.length-1);
}
下面我們來證明一下歸并排序的時間復雜度卷中,我們假設元素個數(shù)n是2的冪,這樣總是能將數(shù)組分為相等的兩部分皆看。
當n=1,歸并排序的時間 T(1)=1 ;
對于任意n個元素歸并排序的時間是兩個n2n2大小歸并排序的時間加上合并的時間仓坞。容易看出合并的時間是線性的,因為合并連個數(shù)組時腰吟,最多進行N-1比較无埃,即每比較依次肯定會有一個數(shù)加入到臨時數(shù)組中去的。
T(n)=T(n2n2)+n
等式兩邊同除以n毛雇,
T(n)nT(n)n=T(n/2)n/2T(n/2)n/2+1
該方程對2的冪的任意n都是成立的嫉称,我們每次除2可以得到下面的一系列等式:
T(n/2)n/2T(n/2)n/2=T(n/4)n/4T(n/4)n/4+1
T(n/4)n/4T(n/4)n/4=T(n/8)n/8T(n/8)n/8+1
…
T(2)2T(2)2=T(1)1T(1)1+1
明顯這些等式一共有l(wèi)ogn個。
然后把所有這些等式相加灵疮,消去左邊和右邊相等的項织阅,所得結果為T(n)nT(n)n=T(1)1T(1)1+logn
稍作變?yōu)門(n)=nlogn+n=O(nlogn)
另外歸并排序需要O(n)的空間復雜度,是一種穩(wěn)定的排序算法震捣。
堆排序
將初始數(shù)組構造成最大堆荔棉,第一趟排序,將堆頂元素arr[0]和堆底元素arr[n-1]交換位置蒿赢,然后將再將arr[0]往下調整润樱,使得剩余的n-1個元素還是堆;第i趟時羡棵,arr[0]與arr[n-i]交換壹若,arr[0]往下調整,使得剩余的n-i個元素還是堆皂冰;直到堆中只剩一個元素結束店展。
public static void heapSort(int[] arr) {
int n = arr.length;
// 構建初始堆
for (int i = (n - 1) / 2; i >= 0; i--)
percDown(arr, i, n - 1);
// 排序,其實相當于每次刪除最大元素秃流,然后將剩下的最后一個元素換到0位置赂蕴,重新調整
for (int i = 1; i < n; i++) {
swap(arr, 0, n - i);
percDown(arr, 0, n - i - 1);
}
}
/**
* @param arr
* 數(shù)組
* @param i
* 要調整的那個元素的位置
* @param n
* 堆最后一個元素的角標
*/
private static void percDown(int[] arr, int i, int n) {
int temp = arr[i];
int child = 2 * i + 1;
while (child <= n) {
if (child < n && arr[child] < arr[child + 1])
child++;
if (temp < arr[child]) {
arr[i] = arr[child];
i = child;// 讓i指向當前child的位置
child = 2 * i + 1;// 獲得新的child
}else{
break;
}
}
arr[i] = temp;
}
percDown函數(shù)時間復雜度不超過O(logn),構造堆的最多時間為O(nlogn)。排序部分進行n-1趟舶胀,也是O(nlogn),所以總的時間復雜度還會O(nlogn)概说。
一趟排序可以確定一個元素的最終位置,堆排序是不穩(wěn)定的排序算法峻贮。
希爾排序
簡單來說就是分組插入排序席怪,它通過比較相距一定間隔的元素來工作;各趟比較所用的距離隨著算法的進行而減小纤控,直到只比較相鄰元素的最后一趟排序為止挂捻,因此也叫作縮減增量排序。
關于增量序列h1船万,h2刻撒,h3骨田,….,ht 只要是h1=1等任何增量序列都是可行的,因為最后一趟h1=1声怔,那么進行的工作就是插入排序啊态贤。
看到這里你也許會好奇,其實希爾排序最后一趟和插入排序做的工作就是一模一樣啊醋火,為什么在選取某些增量序列悠汽,比如Hibbard增量(1,3,7,…,2k2k-1)的情況下芥驳,時間復雜度為O(n32n32) 柿冲。
插入排序的性質:
插入排序在對幾乎已經排好序的數(shù)據(jù)操作時,效率高兆旬,即可以達到線性排序的效率假抄。
但插入排序一般來說是低效的,因為插入排序每次只能將數(shù)據(jù)移動一位丽猬。
所以希爾排序每趟做的工作宿饱,會對下一趟的排序有幫助,并且希爾排序能一次移動消除多個逆序對脚祟。
這里還是選用很常見的序列 ht=N/2,hk=hk+1/2,選用這個增量序列谬以,算法復雜度為O(n2n2)。
代碼如下:
public static void shellSort(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[i];
while (j >= gap && temp < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = temp;
}
}
}
我們知道一次插入排序是穩(wěn)定的愚铡,不會改變相同元素的相對順序蛉签,但在不同的插入排序過程中胡陪,相同的元素可能在各自的插入排序中移動沥寥,最后其穩(wěn)定性就會被打亂,所以shell排序是不穩(wěn)定的