九大經典算法之冒泡排序、快速排序

03 冒泡排序(Bubble Sort)

每次選擇兩個元素，按照需求進行交換（比如需要升序排列的話，把較大的元素放在靠后一些的位置），循環 n 次（n 為總元素個數），這樣小的元素會不斷 “冒泡” 到前面來。

普通版

void bubbleSort(int arr[],int n){//標準版for(int i = 0; i < n - 1; i++){for(int j = 0; j < n - 1 - i; j++){if(arr[j] > arr[j+1]){arr[j] += arr[j+1];arr[j+1] = arr[j] - arr[j+1];arr[j] -= arr[j+1];}}}    
}

進階版

void bubbleSort(int arr[],int n)
{bool swapp = true;while(swapp){swapp = false;for (int  i = 0; i < n - 1; i++) { //這里的n要減1if (arr[i] > arr[i+1] ){arr[i] += a[i+1];arr[i+1] = arr[i] - arr[i+1];arr[i] -=a[i+1];swapp = true;}}}
}

空間效率：O(1)

時間效率：最好情況：O(n)? ?? ? ? ? ? 平均情況：O(N^2)? ? ??? ? ? ? ? ? ? ? ?最壞情況：O(N^2)

穩定性（相同元素相對位置變化情況）：穩定

04 快速排序（Quick Sort）

快排是一個分治的算法，快排算法每次選擇一個元素并且將整個數組以那個元素分為兩部分，整個快速排序的核心是分區（partition），分區的目的是傳入一個數組和選定的一個元素，把所有小于那個元素的其他元素放在左邊，大于的放在右邊。

根據實現算法的不同，元素的選擇一般有如下幾種：

? ? ? 1. 永遠選擇第一個元素

? ? ? 2. 永遠選擇最后一個元素

? ? ? 3. 隨機選擇元素

? ? ? 4. 取中間值

int partition(int arr[], int low, int high){int tmp = arr[low];while (low < high) {            while (low < high && arr[high] >= tmp) {high--;}            arr[low] = arr[high];            while (low < high && arr[low] <= tmp) {low++;}            arr[high] = arr[low];}        arr[low] = tmp;return low; }
void quick_sort(int arr[], int low, int high){if(low < high){int pivotpos = partition(arr,low,high);quick_sort(arr,low,pivotpos-1);quick_sort(arr,pivotpos+1,high);}
}

修改統一接口

void quickSort(int arr[],int n){quick_sort(arr,0,n-1);
}
void quick_sort(int arr[],int low,int high){if(low < high){int pivotpos = partition(arr,low,high);quick_sort(arr,low,pivotpos-1);quick_sort(arr,pivotpos+1,high);}
}int partition(int arr[],int low,int high){int tmp = arr[low];while(low < high){while(low < high && arr[high] >= tmp){high--;}arr[low] = arr[high];while(low < high && arr[low] <= tmp){low++;}arr[high] = arr[low];}arr[low] = tmp;return low;
}

?

算法導論中提供了另一種??partition 的思路

int partition(int arr[], int low, int high){int pivot = arr[high];int i = low - 1;for(int j = low; j <= high - 1; j++){if(arr[j] <= pivot){i++;arr[i] += arr[j];arr[j] = arr[i] - arr[j];arr[i] = arr[i] - arr[j];}} int  temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return (i+1);
}

具體代碼實現

 int partition(int arr[],int low,int high){int pivot = arr[high];int i = low - 1;for(int j = low; j <= high - 1; j++){if(arr[j] <= pivot){i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;//arr[i] += arr[j];  這種交換數值結果出錯 //arr[j] = arr[i] - arr[j];//arr[i] -= arr[j];
          }}int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;//arr[i+1] += arr[high];//arr[high] = arr[i+1] - arr[high];//arr[i+1] -= arr[high];return i+1;}

空間效率：最好情況:? ?O(log₂(N+1))? ? 平均情況 :?O(log₂N)?? ? ? ? ? ? ? ? ? ? 最壞情況 ：?O(log₂N)??

時間效率：最好情況：O(Nlog₂N)??? ? ? ? ? ? ? ? 平均情況：O(Nlog₂N)?? ? ? ? ? ? ? ? ? ? ? 最壞情況：O(N²)

穩定性（相同元素相對位置變化情況）：穩定