數據結構與算法快速排序?假設含有n個記錄的序列為{r1，r2，……，rn}，其相應的關鍵字分别為{k1，k2，……，kn}，需确定1，2，……，n的一種排列p1，p2，……，pn，使其相應的關鍵字滿足kp1≤kp2≤……≤kpn（非遞減或非遞增）關系，即使得序列成為一個按關鍵字有序的序列{rp1，rp2，……，rpn}，這樣的操作就稱為排序，下面我們就來說一說關于數據結構與算法快速排序?我們一起去了解并探讨一下這個問題吧!

數據結構與算法快速排序

假設含有n個記錄的序列為{r1，r2，……，rn}，其相應的關鍵字分别為{k1，k2，……，kn}，需确定1，2，……，n的一種排列p1，p2，……，pn，使其相應的關鍵字滿足kp1≤kp2≤……≤kpn（非遞減或非遞增）關系，即使得序列成為一個按關鍵字有序的序列{rp1，rp2，……，rpn}，這樣的操作就稱為排序。

内排序是在排序整個過程中，待排序的所有記錄全部被放置在内存中。外排序是由于排序的記錄個數太多，不能同時放置在内存，整個排序過程需要在内外存之間多次交換數據才能進行

内排序：插入排序、交換排序、選擇排序和歸并排序

兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止

簡單選擇排序法（Simple Selection Sort）就是通過n－i次關鍵字間的比較，從n－i＋1個記錄中選出關鍵字最小的記錄，并和第i（1≤i≤n）個記錄交換之

将一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增1的有序表

基本有序：就是小的關鍵字基本在前面，大的基本在後面，不大不小的基本在中間

這其實就是希爾排序的精華所在，它将關鍵字較小的記錄，不是一步一步地往前挪動，而是跳躍式地往前移

每次都進行的是間斷的跳躍式變換，而不是相鄰的

堆是具有下列性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆（例如圖9-7-2左圖所示）；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆

将待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根結點。将它移走（其實就是将其與堆數組的末尾元素交換，此時末尾元素就是最大值），然後将剩餘的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次小值。如此反複執行，便能得到一個有序序列了

歸并排序（Merging Sort）就是利用歸并的思想實現的排序方法。它的原理是假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整數）個長度為2或1的有序子序列；再兩兩歸并，……，如此重複，直至得到一個長度為n的有序序列為止，這種排序方法稱為2路歸并排序。

通過一趟排序将待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的