1、排序的定義：假設含有n個記錄的序列為{r1,r2,......,rn}，其相應的關鍵字分別為{k1,k2,......,kn}，需確定1,2,......,n的一種排列p1,p2,......,pn，使其相應的關鍵字滿足kp1<=kp2<=......<=kpn非遞增或非遞減）關系，即使得序列成為一個按關鍵字有序的序列{rp1,rp2,......,rpn}，這樣的操作稱為排序。
2、排序的穩定性：假設關鍵字ki=kj(i!=j)，且在排序前的序列中ri領先於rj，如果排序後ri仍然領先於rj，則稱所用的排序方法是穩定的；反之，若可能使得排序後的序列中rj領先ri，則稱所用的方法是不穩定的。簡單的說，小明和小芳的總分相等，排序前小明排在小芳前面，則排序後小明也在小芳前面，則稱排序算法是穩定的，否則算法是不穩定當。
3、內排序和外排序：內排序是在整個排序過程中，待排序的所有記錄全部放置在內存中。外排序是由於排序的記錄個數太多，不能同時放置在內存，整個排序過程需要在內外寸之間多次交換數據才能進行。
內排序主要受3個方面的影響。
1）時間性能。在內排序中，主要進行兩種操作：比較和移動。總之在排序過程中要盡可能的減少比較的次數，盡可能的減少移動的次數。
2）輔助空間。存放待排序的數據所需的空間以及執行算法時所需要的其他存儲空間。
3）算法的復雜性。這裡指算法本身的復雜度，而不是算法的時間復雜度。顯然算法過於復雜也會影響排序的性能。
4、排序算法的分類
1）交換排序：冒泡排序，快速排序。
2）插入排序：直接插入排序，折半插入排序，希爾排序。
3）選擇排序：簡單選擇排序，堆排序。
4）歸並排序：歸並排序。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282052
