排序

排序是計(jì)算機(jī)的一種操作方法，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列，主要分為內(nèi)部排序和外部排序。

（1）冒泡排序（起泡排序）

冒泡排序（Bubble Sort），其基本思路是，對于一組要排序的元素列，依次比較相鄰的兩個(gè)數(shù)，將比較小的數(shù)放在前面，比較大的數(shù)放在后面，如此繼續(xù)，直到比較到最后的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面，重復(fù)步驟，直至全部排序完成。

優(yōu)點(diǎn)：穩(wěn)定；缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)。

假設(shè)要對含有n個(gè)數(shù)的序列進(jìn)行升序排列，冒泡排序算法步驟是：

①從存放序列的數(shù)組中的第一個(gè)元素開始到最后一個(gè)元素，依次對相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換兩數(shù)的位置；

②第①趟結(jié)束后，最大數(shù)就存放到數(shù)組的最后一個(gè)元素里了，然后從第一個(gè)元素開始到倒數(shù)第二個(gè)元素，依次對相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換兩數(shù)的位置；

③重復(fù)步驟①n-1趟，每趟比前一趟少比較一次，即可完成所求。

1、任意讀入10個(gè)整數(shù)，將其用冒泡法按升序排列后輸出。

2、傳統(tǒng)方法：

（2）選擇法排序

選擇排序法是每一趟在n-i+1（i=1，2，…n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。基于此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。

優(yōu)點(diǎn)：移動(dòng)數(shù)據(jù)的次數(shù)已知（n-1次）；

缺點(diǎn)：比較次數(shù)多，不穩(wěn)定。

選擇法排序是相對好理解的排序算法。假設(shè)要對含有n個(gè)數(shù)的序列進(jìn)行升序排列，算法步驟是：

①從數(shù)組存放的n個(gè)數(shù)中找出最小數(shù)的下標(biāo)（算法見下面的“求最值”），然后將最小數(shù)與第1個(gè)數(shù)交換位置；

②除第1個(gè)數(shù)以外，再從其余n-1個(gè)數(shù)中找出最小數(shù)（即n個(gè)數(shù)中的次小數(shù)）的下標(biāo)，將此數(shù)與第2個(gè)數(shù)交換位置；

③重復(fù)步驟①n-1趟，即可完成所求。

1、任意讀入10個(gè)整數(shù)，將其用選擇法按升序排列后輸出。

2、傳統(tǒng)方法：

函數(shù)法：

（3）插入法排序

優(yōu)點(diǎn)：穩(wěn)定，快；

缺點(diǎn)：比較次數(shù)不一定，比較次數(shù)越多，插入點(diǎn)后的數(shù)據(jù)移動(dòng)越多，特別是當(dāng)數(shù)據(jù)總量龐大的時(shí)候，但用鏈表可以解決這個(gè)問題。

要想很好地掌握此算法，先請了解“有序序列的插入算法”，就是將某數(shù)據(jù)插入到一個(gè)有序序列后，該序列仍然有序。插入算法參見下面的“數(shù)組元素的插入”。

1、將任意讀入的整數(shù)x插入一升序數(shù)列后，數(shù)列仍按升序排列。

插入法排序的要領(lǐng)就是每讀入一個(gè)數(shù)立即插入到最終存放的數(shù)組中，每次插入都使得該數(shù)組有序。

2、任意讀入10個(gè)整數(shù)，將其用插入法按降序排列后輸出。

（4）歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并

即將兩個(gè)都升序（或降序）排列的數(shù)據(jù)序列合并成一個(gè)仍按原序排列的序列。

1、有一個(gè)含有6個(gè)數(shù)據(jù)的升序序列和一個(gè)含有4個(gè)數(shù)據(jù)的升序序列，將二者合并成一個(gè)含有10個(gè)數(shù)據(jù)的升序序列。

（5）字符數(shù)組：（逆序排列）如：<ABCDE-EDCBA>

1、把輸入的字符串逆序排列，如輸入ABCDE，輸出為EDCBA