1. 排序基本概念

現(xiàn)實生活中排序很重要，例如:淘寶按條件搜索的結果展示等。

• 概念
  排序是計算機內經常進行的一種操作，其目的是將一組“無序”的數(shù)據元素調整為“有序”的數(shù)據元素。

• 排序數(shù)學定義：
  假設含 n 個數(shù)據元素的序列為( R1, R2，… Rn) 其相應的關鍵字序列為( K1, K2，., Kn)，這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系：Kp1≤Kp2≤…≤Kpn
  按此固有關系將上式記錄序列重新排列為(Rp1,Rp2，…，Rpn)的操作稱作排序

• 排序的穩(wěn)定性
  如果在序列中有兩個數(shù)據元素r[i]和r[j]，它們的關鍵字 k[i]==k[j]，且在排序之前，對象 r[i]排在r[j]前面。如果在排序之后，對象 r[i]仍在r[j]前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。
  

• 多關鍵字排序
  排序時需要比較的關鍵字多余一個，排序結果首先按關鍵字 1 進行排序，當關鍵字1相同時按關鍵字 2 進行排序，當關鍵字 n-1 相同時按關鍵字n進行排序，對于多關鍵字排序，只需要在比較操作時同時考慮多個關鍵字即可 !

• 排序中的關鍵操作

  • 比較：任意兩個數(shù)據元素通過比較操作確定先后次序。
  • 交換：數(shù)據元素之間需要交換才能得到預期結果

• 內排序和外排序

  • 內排序：在排序過程中，待排序的所有記錄全部都放置在內存中，排序分為：內排和外排序。
  • 外排序：由于排序的記錄個數(shù)太多，不能同時放置在內存，整個排序過程需要在內外存之間多次交換數(shù)據才能進行。

• 排序的審判

  • 時間性能：關鍵性能差異體現(xiàn)在比較和交換的數(shù)量
  • 輔助存儲空間：為完成排序操作需要的額外的存儲空間，必要時可以“空間換時間”
  • 算法的實現(xiàn)復雜性：過于復雜的排序法會影響代碼的可讀性和可維護性，也可能影響排序的性能

• 總結

  • 排序是數(shù)據元素從無序到有序的過程
  • 排序具有穩(wěn)定性，是選擇排序算法的因素之一
  • 比較和交換是排序的基本操作
  • 多關鍵字排序與單關鍵字排序無本質區(qū)別
  • 排序的時間性能是區(qū)分排序算法好壞的主要因素

2. 冒泡排序

冒泡排序就是相鄰兩個元素進行交換，可以從上往下冒，也可以從下往上冒，下圖為一個循環(huán)的冒泡。

2.1 核心代碼

//冒泡排序
void bubble_sort(int arr[], int length)
{for (int i = 0; i < length - 1; i++){for (int j = 0; j < length - i - 1; j++){//此處為升序，降序的話arr[j] < arr[j + 1]if (arr[j] > arr[j + 1])  //升序{swap(&arr[j], &arr[j + 1]);}}}
}

2.2 冒泡排序代碼

實現(xiàn)冒泡排序的代碼如下

#include <iostream>
#include <time.h>
using namespace std;#define MAX 10void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//打印數(shù)組
void printArr(int arr[])
{for (int i = 0; i < 10; i++){cout << arr[i] << endl;}
}//冒泡排序
void bubble_sort(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])  //升序{swap(&arr[j], &arr[j + 1]);}}}printArr(arr);
}int main()
{int arr[MAX];//生成隨機數(shù)srand((unsigned int)time(NULL));for (int i=0;i<MAX;i++){arr[i] = rand() % MAX;}bubble_sort(arr, MAX);system("pause");return 0;
}

2.3 查看冒泡排序的時間消耗

敲代碼查看冒泡排序的時間消耗

#include <iostream>
#include <time.h>
#include <sys/timeb.h>using namespace std;#define MAX 10000//獲取系統(tǒng)當前時間,ms為單位
long getSystemTime()
{struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm;
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//打印數(shù)組
void printArr(int arr[])
{for (int i = 0; i < 10; i++){cout << arr[i] << endl;}
}//冒泡排序
void bubble_sort(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])  //升序{swap(&arr[j], &arr[j + 1]);}}}//printArr(arr);
}int main()
{int arr[MAX];//生成隨機數(shù)srand((unsigned int)time(NULL));for (int i=0;i<MAX;i++){arr[i] = rand() % MAX;}long tStart = getSystemTime();bubble_sort(arr, MAX);long tEnd = getSystemTime();cout << tEnd - tStart << endl;system("pause");return 0;
}

運行結果：3247ms

2.4 冒泡排序改進版減小時間消耗

下圖中，當9排到第一個就已經是有序的了。之前的版本每一個都需要進行比較，我們可以判斷其在有序的情況下就可以退出了，沒有必要一直比較循環(huán)。這樣就提高了冒泡排序的效率。

在核心代碼中有一次循環(huán)并不執(zhí)行swap(&arr[j], &arr[j + 1]);就代表已經有序了

int flag=0;//標識沒有排序好
//冒泡排序
void bubble_sort(int arr[], int length)
{for (int i = 0; i < length - 1 && flag==0; i++){for (int j = 0; j < length - i - 1; j++){flag = 1;//認為已經排序好//此處為升序，降序的話arr[j] < arr[j + 1]if (arr[j] > arr[j + 1])  //升序{flag=0;swap(&arr[j], &arr[j + 1]);}}}
}

整體代碼為：

#include <iostream>
#include <time.h>
#include <sys/timeb.h>using namespace std;#define MAX 10000//獲取系統(tǒng)當前時間,ms為單位
long getSystemTime()
{struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm;
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//打印數(shù)組
void printArr(int arr[])
{for (int i = 0; i < 10; i++){cout << arr[i] << endl;}
}int flag = 0;//標識沒有排序好
//冒泡排序
void bubble_sort(int arr[], int length)
{for (int i = 0; i < length - 1 && flag == 0; i++){for (int j = 0; j < length - i - 1; j++){flag = 1;//認為已經排序好//此處為升序，降序的話arr[j] < arr[j + 1]if (arr[j] > arr[j + 1])  //升序{flag = 0;swap(&arr[j], &arr[j + 1]);}}}
}int main()
{int arr[MAX];//生成隨機數(shù)srand((unsigned int)time(NULL));for (int i=0;i<MAX;i++){arr[i] = rand() % MAX;}long tStart = getSystemTime();bubble_sort(arr, MAX);long tEnd = getSystemTime();cout << tEnd - tStart << endl;system("pause");return 0;
}

運行結果：1800ms，耗時變?yōu)樵鹊囊话?br />

3. 排序基本概念，冒泡排序，冒泡排序改進版
4. 參考博文：常見的幾種排序（C++