1.排序算法的分類
內(nèi)排序和外排序概念
內(nèi)排序：指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序浓冒。
外排序：指在排序期間全部對象太多，不能同時存放在內(nèi)存中尖坤，必須根據(jù)排序過程的要求稳懒，不斷在內(nèi)，外存間移動的排序慢味。
2.排序算法思想和實現(xiàn)
我們平時面試時遇到的大多數(shù)是內(nèi)排序场梆，現(xiàn)在總結(jié)一個內(nèi)排序各個方法的思想和實現(xiàn)。
（1）直接插入排序法
算法思想：每趟 將一個待排序的元素作為關(guān)鍵字纯路，按照其關(guān)鍵字的大小插入到已經(jīng)排好的部分序列的適當(dāng)位置上或油，直到插入完成。
void InsertSort(int R[],int n){ //待排數(shù)據(jù)存在R[]中驰唬，默認為整型装哆，個數(shù)n
int i,j;
int temp;
for(i=2;i<=n;++i){ //數(shù)組從下標(biāo)1 開始存儲，第一個元素有序定嗓，所以從第二個開始處理
temp=R[i]; //將待插入元素暫存于temp中
j=i-1;
/*下面這個循環(huán)完成了從待排元素之前的元素開始掃描蜕琴，如果大于待排元素，則后移一位*/
while(j>=1&&temp<R[j]){
R[j+1]=R[j];
--j;
}
R[j+1]=temp; //找到插入位置宵溅，將temp中暫存的待排元素插入
}
}
（2）二分法插入排序(也叫折半插入排序)
算法思想：基本思想和直接插入排序一樣凌简，區(qū)別在于尋找插入位置的方法不同；二分插入排序采用二分法查找插入位置恃逻。
/*** 折半插入排序 */
private static void binaryInsertSort ( int[] array,int n ) {
for ( int i = 1; i < n; i++ ){
// if (array[i] > array[i - 1]) // 從大到小
if (array[i] < array[i - 1]) { // 從小到大
int tmp = array[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = ( low + high ) >>> 1; // if (array[mid] > tmp) // 從大到小
if (array[mid] < tmp){ // 從小到大
low = mid + 1;
} else {
high = mid - 1;
}
}
for ( int j = i; j > low; j-- ){
array[j] = array[j - 1];
}
array[low] = tmp;
}
}
}
（3）希爾排序
希爾排序又稱為縮小增量排序雏搂，也屬于插入排序類的算法，是對直接插入排序的一種改進寇损。
算法思想：將需要排序的序列劃分為若干個較小的序列凸郑，對這些序列進行直接插入排序，通過這樣的操作可使用需要排序的數(shù)列基本有序矛市，最后再使用一次直接插入排序芙沥。
void shellInsert (list R,int n, int h){ //一趟插入排序，h為本趟增量
int i, j, k;
for (i = 1; i <= h; i++) { //i為組號
for (j = h; j <= n; j += h) { //每組從第二個記錄開始插入
if (R[j].key >= R[j - h].key) continue; //R[j]大于有序區(qū)的最后一個記錄浊吏，不需要插入
R[0] = R[j];
k = j - h;
do {
R[k + h] = R[k];
k = k - h; //后移記錄繼續(xù)向前搜索
} while ( k > 0 && R[0].key < R[k].key;);
R[k + h] = R[0];
}
}
}
（4）直接選擇排序
算法思想：對n個記錄進行掃描而昨，選擇最小的記錄，將其輸出找田，接著在剩下的n-1個記錄中掃描歌憨，選擇最小的記錄將其輸出，……不斷重復(fù)這個過程墩衙，直到只剩一個記錄為止务嫡。
void selectSort(int[] array,int n) {
int min;
int tmp = 0;
for (int i = 0; i < n; i++) {
min = array[i];
for (int j = i; j < n; j++) {
if (array[j] < min) {
min = array[j];//最小值
tmp = array[i];
array[i] = min;
array[j] = tmp;
}
}
}
}
（5）堆排序
堆是一個完全二叉樹甲抖，樹中每個結(jié)點對應(yīng)于原始數(shù)據(jù)的一個記錄，并且每個結(jié)點應(yīng)滿足以下條件：非葉結(jié)點的數(shù)據(jù) 大于或等于其左心铃、右孩子結(jié)點的數(shù)據(jù)（若是按從大到小的順序排序准谚，則要求非葉結(jié)點的數(shù)據(jù)小于或等于其左、右孩子結(jié)點的數(shù)據(jù)）
由堆的定義可看出于个，其根結(jié)點為最大值氛魁，堆排序就是利用這一特點進行的。堆排序過程包括兩個階段：
①將無序的數(shù)據(jù)構(gòu)成堆（即用無序數(shù)據(jù)生成滿足堆定義的完全二叉樹）厅篓。
②利用堆排序（即用上一步生成的堆輸出有序的數(shù)據(jù)）秀存。
void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {
//建立父節(jié)點指標(biāo)和子節(jié)點指標(biāo)
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點指標(biāo)在范圍內(nèi)才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節(jié)點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節(jié)點大於子節(jié)點代表調(diào)整完畢羽氮，直接跳出函數(shù)
return;
else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i; //初始化或链，i從最後一個父節(jié)點開始調(diào)整
for (i = len / 2 - 1; i >= 0; i--) //建堆 ： len/2-1是最后一個非葉子節(jié)點位置
max_heapify(arr, i, len - 1);
//先將第一個元素和已排好元素前一位做交換，再重新調(diào)整档押，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
（6）冒泡排序
算法思想：
第一個記錄和第二個記錄比澳盐，如果第一個大，則二者交換令宿，否則不交換叼耙；然后第二個記錄和第三個記錄比較，如果第二個大粒没，則交換筛婉，否則不交換。癞松。爽撒。一直這樣進行下去（冒泡排序算法的結(jié)束條件是在一趟排序過程中沒有發(fā)生元素交換）。
void BubblSort(int[], int n){
int i,j,flag; int temp;
for (i = n; i >= 2; i--){ //數(shù)組從下標(biāo)1開始存儲
flag = 0;
for (j = 2; j <= i; ++j){
if (R[j - 1] > R[j]) {
temp = R[j];
R[j] = R[j - 1];
R[j - 1] = temp; //交換
flag = 1;//如果發(fā)生交換响蓉，flag為1硕勿，沒有發(fā)生交換，值為0
}
if (flag == 0) {
return;
}
}
}
}
（7）快速排序
算法思想：
快速排序使用分治策略來把待排序數(shù)據(jù)序列分為兩個子序列枫甲，具體步驟為：
- 在數(shù)據(jù)集之中源武，選擇一個元素作為”基準”。
- 所有小于”基準”的元素言秸，都移到”基準”的左邊软能；所有大于”基準”的元素，都移到”基準”的右邊举畸。分區(qū)操作結(jié)束后，基準元素所處的位置就是最終排序后它的位置凳枝。
- 對”基準”左邊和右邊的兩個子集抄沮，不斷重復(fù)第一步和第二步跋核，直到所有子集只剩下一個元素為止。
void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //將數(shù)組分為兩部分
qsort(arr, low, pivot-1); //遞歸排序左子數(shù)組
qsort(arr, pivot+1, high); //遞歸排序右子數(shù)組
}
}
int partition(int[] arr, int low, int high){
int pivot = arr[low]; //樞軸記錄
while (low<high){
while (low<high && arr[high]>=pivot) --high;
arr[low]=arr[high]; //交換比樞軸小的記錄到左端
while (low<high && arr[low]<=pivot) ++low;
arr[high] = arr[low]; //交換比樞軸小的記錄到右端
}
//掃描完成叛买，樞軸到位
arr[low] = pivot;
//返回的是樞軸的位置
return low;
}
（8）歸并排序
算法思想：把待排序的文件分成若干個子文件砂代，先將每個子文件內(nèi)的記錄排序，再將已排序的子文件合并率挣，逐個得到完整的排序文件刻伊。
public void mergeSort(int[] a,int left,int right,int n){ //n為數(shù)組長度
if(left<right){
int middle = (left+right)/2;
mergeSort(a, left, middle);
mergeSort(a,middle+1,right);
merge(a,left,middle,right,n);//合并
}
}
void merge(int[] a, int left, int middle, int right,int n) {
int [] tmpArray = new int[n];
int rightStart = middle+1;
int tmp = left;
int third = left;
//比較兩個小數(shù)組相應(yīng)下標(biāo)位置的數(shù)組大小，小的先放進新數(shù)組
while(left<=middle&&rightStart<=right){
if(a[left]<=a[rightStart]){
tmpArray[third++] = a [left++];
}else{
tmpArray[third++] = a[rightStart++];
}
}
//如果左邊還有數(shù)據(jù)需要拷貝椒功，把左邊數(shù)組剩下的拷貝到新數(shù)組
while(left<=middle){
tmpArray[third++] = a[left++];
}
//如果右邊還有數(shù)據(jù)......
while(rightStart<=right){
tmpArray[third++] = a[rightStart++];
}
while(tmp<=right){
a[tmp] = tmpArray[tmp++];
}
}
（9）桶排序
將數(shù)組分到有限數(shù)量的桶里捶箱，每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列动漾。
void bucketSort ( int[] array, int min, int max,int n)
{
int[] tmp = new int[n];
int[] buckets = new int[max - min];
for ( int i = 0; i < n; i++ )
{
buckets[array[i] - min]++;
}
// 從小到大
// for ( int i = 1; i < max - min; i++ )
// {
// buckets[i] = buckets[i] + buckets[i - 1];
// }
// 從大到小
for ( int i = max - min - 1; i > 0; i-- )
{
buckets[i - 1] = buckets[i] + buckets[i - 1];
}
System.arraycopy (array, 0, tmp, 0, n);
for ( int k = array.length - 1; k >= 0; k-- )
{
array[--buckets[tmp[k] - min]] = tmp[k];
}
}
（10）基數(shù)排序（低位優(yōu)先分配排序法）
基數(shù)排序：排序采用的主要數(shù)據(jù)結(jié)構(gòu)是單鏈表表示的隊列丁屎。
算法思想：把排序碼分解成若干部分，然后通過對各個部分排序碼的分別排序旱眯，最終實現(xiàn)對整個排序碼的排序晨川。
實現(xiàn)排序的方法：①高位優(yōu)先法：從最高位排序碼 k(0) 開始，逐個針對各個排序碼排序共虑。②地位優(yōu)先法：從最低位排序碼 k(d-1) 開始排序
struct Node{
KeyType key[D];//排序碼是數(shù)組
DataType info;
PNode next;
}
typedef struct{
PNode f;//隊列頭指針
PNode e;//隊列尾指針
}Queue; //用隊列表示各個子序列
typedef struct Node *RadixList; //待排序文件類型
void radixSort(RadixList *plist,int d,int r){
int i,j,k; PNode p,head=(*plist)->next;
final Queue queue[r];//隊列數(shù)組
for(j=d-1;j>=0;j--){//進行d次分配和收集
for(i=0;i<r;i++){
queue[i].f=queue[i].e=null;//清空隊列
}
for(p=head;p!=null;p=p->next){
k=p->key[j]; //按排序碼的第j個分量分配
if(queue[k].f==null){
queue[k].f=p;//隊列為空設(shè)隊頭指針
}else {
(queue[k].e)->next=p; //接到隊列k尾
}
queue[k].e=p;
}
for(i=0;queue[i].f==null;i++);//找到第一個非空數(shù)列
p=queue[i].e; head =queue[i].f; //head為收集鏈表的頭指針
for(i++;i<r;i++){
if (queue[i].f!=null){
p->next=queue[i].f;
p=queue[i].e;
}
}
p->next=null;
}
(*plist)->next=head;
}
