本章節(jié)涵蓋了冒泡排序O(n^2) 庙洼、選擇排序O(n^2) 、插入排序O(n^2)、快速排序O(nlogn)和歸并排序O(nlogn)的內(nèi)容钧忽。
其中工程上用得最多的是插入排序和快速排序。而在寫算法題的時(shí)候簡單排序可以考慮直接使用庫函數(shù)sort(首元素地址逼肯，尾元素地址的下一個(gè)地址耸黑，比較函數(shù))，其中最后一個(gè)參數(shù)“比較函數(shù)”非必填篮幢。
比如針對int a[] = {3,2,1,4}, 想要升序排序下標(biāo)[0,2]這三個(gè)元素大刊，那么需要調(diào)用sort(a, a+3)
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
vector<int> Arr;
bool cmp(int a, int b){
return a>b;
}
int main(){
Arr.push_back(3);
Arr.push_back(1);
Arr.push_back(2);
sort(Arr.begin(), Arr.end());
for (int i=0; i<Arr.size();i++){
printf("%d ", Arr[i]);
}
printf("\n");
sort(Arr.begin(), Arr.end(),cmp);
for (int i=0; i<Arr.size();i++){
printf("%d ", Arr[i]);
}
printf("\n");
int a[8] = {2,4,5,1,3,9,4,-1};
sort(a, a+7);
for (int i=0; i<8;i++){
printf("%d ", a[i]);
}
}
輸出結(jié)果依次是
1 2 3
3 2 1
1 2 3 4 4 5 9 -1
1 冒泡排序O(n^2)，穩(wěn)定
當(dāng)題目告訴你n的規(guī)模超過1000的話三椿，就不能用了缺菌。
道理很簡單，針對遞增排序來說搜锰，對數(shù)組一共會(huì)做n-1趟掃描（i=1;i<=n-1;i++）伴郁，每次掃描的時(shí)候，比較的都是相鄰兩個(gè)數(shù)的大械暗稹（a[j] > a[j+1]）焊傅，然后做交換。每趟結(jié)束的時(shí)候狈涮，本趟掃描中的最大值會(huì)像氣泡一樣排到了末尾位置租冠。每趟能夠掃描到的數(shù)是(j=0;j<n-i;j++)。
- 穩(wěn)定
- 做交換的次數(shù) = 逆序?qū)?shù)
- 最好O(N)
- 平均O(n^2)
- 空間O(1)
- 內(nèi)部排序薯嗤，原地排序
題目：7-73 比較大小 (10分)
#include <stdio.h>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
int num[3] = {0};
for (int i=0;i<3;i++){
scanf("%d", &num[i]);
}
for (int i=1;i<=2;i++){
for (int j=0;j<3-i;j++){
if (num[j] > num[j+1]){ // 相等的時(shí)候不做交換顽爹，所以穩(wěn)定
swap(&num[j], &num[j+1]);
}
}
}
printf("%d", num[0]);
for (int i=1;i<3;i++){
printf("->%d", num[i]);
}
return 0;
}
如果掃描一趟就發(fā)現(xiàn)已經(jīng)是遞增序列了，就不繼續(xù)掃描了
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
/* 請?jiān)谶@里填寫答案 */
void sort ( int a[], int len ){
int is_sort = 1;
for (int i = len-1;i>0;i--){
is_sort = 1;
for (int j = 0;j<i;j++){
if (a[j] > a[j+1]){
is_sort = 0;
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
if (is_sort) {
break;
}
}
}
2 選擇排序 O(n^2)
首先在未排序序列中找到最小元素骆姐，存放到排序序列的起始位置镜粤。
再從剩余未排序元素中繼續(xù)尋找最心筇狻（大）元素，然后放到已排序序列的末尾肉渴。
重復(fù)第二步公荧，直到所有元素均排序完畢。
同樣是O(n^2)的算法復(fù)雜度同规，同樣無法處理n的規(guī)模超過1000的無序數(shù)據(jù)循狰。但是冒泡排序針對已經(jīng)排序好的序列，有O(n)復(fù)雜度的優(yōu)勢券勺。
- 不穩(wěn)定
- 無論什么情況下绪钥，都要比較
N*(N-1)/2次 - 最好O(n^2)
- 平均O(n^2)
- 空間O(1)
- 內(nèi)部排序，原地排序
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
/* 請?jiān)谶@里填寫答案 */
void sort ( int a[], int len ){
for (int i=0;i<len;i++){
int min = i;
for (int j = i+1;j<len;j++){
// 找到無序數(shù)組中的最小值
if (a[j] < a[min]){
min = j;
}
}
if (min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
3 直接插入排序 O(n^2)
插入排序也可以引入二分查找進(jìn)行優(yōu)化关炼，或者使用每次交換相隔一定元素的希爾排序程腹。但是這里說的是普通的直接插入排序，或者叫簡單插入排序儒拂。
插入排序假定左側(cè)都是有序的寸潦，比如左側(cè)都是升序[0,2,4,5]， 右側(cè)是等待排序的序列社痛，比如[1,7], 那么1就會(huì)從數(shù)字5開始见转，逐一向左比較，發(fā)現(xiàn)數(shù)字比1大蒜哀，就發(fā)生交換（右移動(dòng)）池户，一直到與數(shù)字0比較發(fā)現(xiàn)小于1為止，然后把1放到0后面的位置凡怎。這個(gè)過程就像打撲克牌時(shí)的摸牌一樣校焦。
簡單插入排序效率不高的主要原因是每次只移動(dòng)相鄰的兩個(gè)元素，這樣只能消去一對錯(cuò)位的元素统倒。希爾排序的改進(jìn)方案是寨典，每次交換相隔一定距離的元素，比如先相隔5房匆，再相隔3耸成，最后相隔1即使用簡單插入排序，到最后相隔1的時(shí)候浴鸿，前面的步驟已經(jīng)交換了很多逆序?qū)狻Ｏ柵判蚴遣环€(wěn)定的，時(shí)間復(fù)雜度的計(jì)算也很復(fù)雜岳链。
針對已經(jīng)排好序的大規(guī)模數(shù)據(jù)花竞，插入排序的表現(xiàn)也是比選擇排序要好，接近O(N)掸哑，而且我們使用不交換數(shù)據(jù)直接賦值的方式進(jìn)行數(shù)據(jù)的插入约急，這也比冒泡排序一個(gè)個(gè)相鄰元素都交換有優(yōu)勢零远。所以冒泡和選擇一般停留在理論上，工程上插入排序是用得更多的厌蔽。
- 穩(wěn)定
- 做交換的次數(shù) = 逆序?qū)?shù)
- 最好O(N) 已經(jīng)有序
- 平均O(N^2)
- 空間O(1)
- 內(nèi)部排序牵辣，原地排序
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
void sort ( int a[], int len ){
for (int i=1;i<len;i++){
int value=a[i];
int j=i;
while (j>0 && a[j-1] > value){
a[j] = a[j-1];
j--;
}
a[j] = value;
}
}
4 快速排序 O(NlogN)，不穩(wěn)定
注意對于有序數(shù)組奴饮，使用快排仍然是O(n^2)時(shí)間復(fù)雜度纬向，也就是說對于n規(guī)模大于1000且已知測試點(diǎn)序列可能有序的情況下，就不要使用快排了
https://www.lintcode.com/problem/sort-integers-ii/description
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
if (A == null || A.length == 0) {
return;
}
quickSort(A, 0, A.length - 1);
}
private void quickSort(int[] A, int start, int end) {
// 已經(jīng)排好序了
if (start >= end) {
return;
}
int left = start, right = end;
// 獲取中間的pivot戴卜，是數(shù)組值逾条，不是下標(biāo)
int pivot = A[(start + (end - start) / 2)];
// 所有都是left <= right，保證掃描結(jié)束兩根指針不重疊叉瘩，而是right在左膳帕，left在右粘捎∞泵澹可能相鄰，也可能相隔一個(gè)數(shù)
while (left <= right) {
// 數(shù)組中的值使用A[left] < pivot攒磨，不使用相等泳桦，保證相等的數(shù)均分
while(left <= right && A[left] < pivot) {
left++;
}
while(left <= right && A[right] > pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
// 最后right會(huì)在left左邊
quickSort(A, start, right);
quickSort(A, left, end);
}
}
當(dāng)序列中的元素接近有序時(shí)，這種選擇pivot的方法時(shí)時(shí)間復(fù)雜度會(huì)退化成O(n^2)娩缰。
找到第K大的數(shù)/中位數(shù)
https://www.lintcode.com/problem/kth-largest-element/description
public class Solution {
/**
* @param n: An integer
* @param nums: An array
* @return: the Kth largest element
*/
public int kthLargestElement(int n, int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
return findKthLargest(nums, 0, nums.length - 1, n);
}
private int findKthLargest(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[start];
}
int left = start, right = end;
int pivot = nums[(start + (end - start) / 2)];
while (left <= right) {
while (left <= right && nums[left] > pivot) {
left++;
}
while (left <= right && nums[right] < pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (start + k - 1 <= right) {
return findKthLargest(nums, start, right, k);
}
if (start + k - 1 >= left) {
return findKthLargest(nums, left, end, k - (left - start));
}
return nums[right+1];
}
}
5 歸并排序 O(NlogN)灸撰，穩(wěn)定
對于序列[1,2,3,1,4] 5個(gè)數(shù)
- 第一趟merge下標(biāo)0~1 得到[1,2]
- 第二趟merge下標(biāo)0~2 得到[1,2,3]
- 第三趟merge下標(biāo)3~4 得到[1,4]
- 第四趟merge下標(biāo)0~4 得到[1,1,2,3,4]
歸并排序需要開辟一個(gè)臨時(shí)數(shù)組，所以這個(gè)數(shù)組不能定義在方法中拼坎，內(nèi)存不夠。
想象2G的內(nèi)存，排序2G的數(shù)據(jù)黔衡，如果使用歸并排序的話奏纪，只有1G的內(nèi)存可以用。歸并排序一般不用于內(nèi)部排序盛龄，是外部排序的有用工具饰迹。
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
int temp[1000000];
void mergeSort(int a[],int left,int right);
void merge(int a[],int l1,int r1,int l2,int r2); // [l1,r1] 和 [l2,r2]
void sort ( int a[], int len ){
mergeSort(a,0,len-1);
}
void mergeSort(int a[],int left,int right){
if (left<right){
int mid = (left+right) >>1;
mergeSort(a,left,mid);
mergeSort(a,mid+1,right);
merge(a,left,mid,mid+1,right);
}
}
void merge(int a[],int l1,int r1,int l2,int r2){
int i=l1,j=l2;
int index = 0;
while (i<=r1 && j<= r2){
if (a[i] <= a[j]){
temp[index++] = a[i++];
} else {
temp[index++] = a[j++];
}
}
// 到此處時(shí)，要么i已經(jīng)等于r1, 要么j已經(jīng)到達(dá)r2
while (i<=r1){
temp[index++] = a[i++];
}
while (j<=r2){
temp[index++] = a[j++];
}
for (i = 0;i<index;i++){
a[l1+i] = temp[i];
}
}
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
if (A == null || A.length == 0) {
return;
}
int temp[] = new int[A.length];
mergeSort(A, 0, A.length - 1, temp);
}
private void mergeSort(int[] A, int left, int right, int[] temp){
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(A, left, mid, temp);
mergeSort(A, mid+1, right, temp);
merge(A, left, mid, mid + 1, right, temp);
}
}
private void merge(int[] A, int lleft, int lright, int rleft, int rright, int[] temp){
int i = lleft, j = rleft;
int index = lleft;
while (i <= lright && j <= rright) {
if (A[i] < A[j]) {
temp[index++] = A[i++];
}else {
temp[index++] = A[j++];
}
}
while(i <= lright) {
temp[index++] = A[i++];
}
while(j <= rright) {
temp[index++] = A[j++];
}
for (int k = lleft; k<= rright; k++) {
A[k] = temp[k];
}
}
}
6 堆排序余舶，O(NlogN)啊鸭，不穩(wěn)定
原地排序方法：
對于一個(gè)N個(gè)元素的無序數(shù)組（下標(biāo)從0~N-1），首先建立大頂堆
- 將堆頂元素和最后一個(gè)元素交換匿值，即堆頂元素?fù)Q到了N-1下標(biāo)
- 對剩下的0~N-2元素重新生成一個(gè)大頂堆
- 將當(dāng)前最大值和第N-2下標(biāo)元素交換
- 繼續(xù)反復(fù)赠制，知道堆中只剩1個(gè)元素，即可停止
