資料結構（C語言版）---排序

1、排序：重排表中元素，

2、根據資料元素是否完全在記憶體中，將排序演算法分為內部排序和外部排序兩類，

3、插入排序：將一個待排序記錄按關鍵字大小插入到前面已排好的子序列中，直到全部記錄插入完成，

1）直接插入排序

void insertsort(sqlist L)
{
 int i, j;
 for (i = 2; i <=L.length; ++i)
 {
  if (L.r[i].key < L.r[i - 1].key)
  {
   L.r[0] = L.r[i];
   L.r[i] = L.r[i - 1];
   for (j = i - 2; L.r[0].key < L.r[j].key; --j)
   {
    L.r[j + 1] = L.r[j];
   }
   L.r[j + 1] = L.r[0];
  }
 }
}

（1）空間復雜度為O(1)；時間復雜度為O(n²)，

（2）穩定性：插入元素時總是從后向前先比較后移動，不會出現相同元素相對位置發生變化，為穩定演算法，

（3）適用性：適用于順序存盤和鏈式存盤的線性表，

2）折半插入排序

void insertsort2(sqlist L)
{
 int i, j, low, high, mid;
 for (i = 2; i < L.length; i++)
 {
  L.r[0] = L.r[i];
  low = 1;
  high = i - 1;
  while (low<=high)
  {
   mid = (low + high) / 2;
   if (L.r[mid].key > L.r[0].key)
   {
    high = mid - 1;
   }
   else
   {
    low = mid + 1;
   }
  }
  for (j = i - 1; j >= high + 1; --j)
  {
   L.r[j + 1] = L.r[j];
  }
  L.r[high + 1] = L.r[0];
 }
}

（1）折半查找找出元素待插入的位置，統一地移動待插入位置之后的所有元素，

（2）時間復雜度為O(n²)，

（3）穩定性：為穩定演算法，

3）希爾排序（縮小增量排序）

void insertsort3(sqlist L)
{
 int i, j,k;
 for (j = L.length / 2; j >= 1; j = j / 2)
 {
  for (i = j + 1; i <= L.length; ++i)
  {
   if (L.r[i].key < L.r[i - j].key)
   {
    L.r[0] = L.r[i];
    for (k = i - j; k > 0 && L.r[0].key < L.r[k].key; k -= j)
    {
     L.r[k + j] = L.r[k];
    }
    L.r[k + j] = L.r[0];
   }
  }
 }
}

（1）將待排序表分割成若干個子表，分別進行直接插入排序，當表中元素節本有序時，對整個表進行一次直接插入排序，

（2）空間復雜度為O(1)；時間復雜度約為O(n^1-2)，最壞情況下時間復雜度為O(n²)，

（3）穩定性：不穩定，

（4）適用性：僅適用于順序存盤的線性表，

4、交換排序

1）冒泡排序

void bubblesort(sqlist L)
{
 int i, j, temp;
 bool flag;//發生交換的標志
 for (i = 0; i < L.length-1; i++)
 {
  flag = false;
  for (j = L.length - 1; j > i; j--)
  {
   if (L.r[j - 1].key > L.r[j].key)
   {
    temp = L.r[j - 1].key;
    L.r[j - 1].key = L.r[j].key;
    L.r[j].key = temp;
    flag = true;
   }
  }
  if (flag == false)
  {
   return;
  }
 }
}

（1）從后向前兩兩比較相鄰元素的值，若為逆序則交換，

（2）空間復雜度為O(1)；平均時間復雜度為O(n²)，最壞情況下時間復雜度為O(n²)，

（3）穩定性：穩定，

（4）雙向起泡排序，奇數趟時，從前向后比較相鄰元素的關鍵字，逆序則交換；偶數趟時，從后向前比較相鄰元素的關鍵字，逆序則交換，

void bubblesort2(sqlist L)
{
 int low = 0, high = L.length;
 bool flag = true;
 int temp;
 while (low<high&&flag)
 {
  flag = false;
  for (int i = low; i < high; i++)
  {
   if (L.r[i].key > L.r[i + 1].key)
   {
    temp = L.r[i].key;
    L.r[i].key = L.r[i+1].key;
    L.r[i+1].key = temp;
    flag = true;
   }
  }
  high--;
  for (int i = high; i >low; i--)
  {
   if (L.r[i].key < L.r[i - 1].key)
   {
    temp = L.r[i].key;
    L.r[i].key = L.r[i - 1].key;
    L.r[i - 1].key = temp;
    flag = true;
   }
  }
  low++;
 }
}

2）快速排序

int partition(sqlist L, int low, int high)
{
 int pivotkey;
 L.r[0] = L.r[low];
 pivotkey = L.r[low].key;
 while (low<high)
 {
  while (low<high&&L.r[high].key>=pivotkey)
  {
   --high;
  }
  L.r[low] = L.r[high];
  while (low < high&&L.r[low].key <= pivotkey)
  {
   ++low;
  }
  L.r[high] = L.r[low];
 }
 L.r[low] = L.r[0];
 return low;
}
void quicksort(sqlist L,int low,int high)
{
 if (low < high)
 {
  int pos = partition(L, low, high);
  quicksort(L, low, pos - 1);
  quicksort(L, pos + 1, high);
 }
}

（1）最壞情況空間復雜度為O(n)，平均空間復雜度為O(log₂n)；平均時間復雜度為O(nlog₂n)，最壞情況下時間復雜度為O(n²)，

（2）所有內部排序中平均性能最優的排序演算法，

5、選擇排序

每一趟在后面n-i+1個待排序元素中選取關鍵字最小的元素，作為有序序列的第i個元素，直到第n-1趟做完，待排序元素只剩一個，

1）簡單選擇排序

void selectsort(sqlist L)
{
 int i, j, min,temp;
 for (i = 0; i < L.length - 1; i++)
 {
  min = i;
  for (j = i + 1; j < L.length; j++)
  {
   if (L.r[j].key < L.r[min].key)
   {
    min = j;
   }
  }
  if (min != i)
  {
   temp = L.r[i].key;
   L.r[i].key = L.r[min].key;
   L.r[min].key = temp;
  }
 }
}

（1）空間復雜度為O(1)；時間復雜度為O(n²)，

（2）穩定性：不穩定，

2）堆排序

void adjustdown(sqlist L,int k)//將元素向下調整
{
 L.r[0].key = L.r[k].key;
 for (int i = 2 * k; i <= L.length; i *= 2)
 {
  if (I < L.length&&L.r[i].key < L.r[i + 1].key)
  {
   i++;
  }
  if (L.r[0].key >= L.r[i].key)
  {
   break;
  }
  else
  {
   L.r[k].key = L.r[i].key;
   k = i;
  }
 }
 L.r[k].key = L.r[0].key;
}

時間復雜度與樹高(h)有關，為O(h)，
void adjustup(sqlist L, int k)//將元素向上調整
{
 L.r[0].key = L.r[k].key;
 int i = k / 2;
 while (i>0&& L.r[i].key < L.r[0].key)
 {
  L.r[k].key = L.r[i].key;
  k = i;
  i = k / 2;
 }
 L.r[k].key = L.r[0].key;
}

void buildmaxheap(sqlist L)//建立大根堆
{
 for (int i = L.length / 2; i > 0; i--)
 {
  adjustdown(L, i);
 }
}

在n個元素序列上建堆，時間復雜度為O(n)，
void heapsort(sqlist L)
{
 buildmaxheap(L);
 int temp;
 for (int i = L.length; i > 1; i--)
 {
  temp = L.r[i].key;
  L.r[i].key = L.r[1].key;
  L.r[1].key = temp;
  adjustdown(L, 1);
 }
}

（1）一種樹形選擇排序，在排序程序中，將L視為一棵完全二叉樹的順序存盤結構，

（2）最大堆：堆頂元素取最大值；最小堆：堆疊頂元素為最小值，

（2）空間復雜度為O(1)；時間復雜度為O(nlog₂n)，

（3）穩定性：不穩定，

6、歸并排序

1）歸并：將兩個或兩個以上的有序表組合成一個新的有序表，

2）2路歸并排序

void merge(sqlist A, int low, int mid, int high)
{
 sqlist B;
 int i, j, k;
 for (k = low; k <= high; k++)
 {
  B.r[k].key = A.r[k].key;
 }
 for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
 {
  if (B.r[i].key <= B.r[j].key)
  {
   A.r[k].key <= B.r[i++].key;
  }
  else
  {
   A.r[k].key <= B.r[j++].key;
  }
 }
 while (i<=mid)
 {
  A.r[k++].key <= B.r[i++].key;
 }
 while (j <= high)
 {
  A.r[k++].key <= B.r[j++].key;
 }
}
void mergesort(sqlist L, int low, int high)
{
 if (low < high)
 {
  int mid = (low + high) / 2;
  mergesort(L, low, mid);
  mergesort(L, mid + 1, high);
  merge(L, low, mid, high);
 }
}

（1）假定帶排序表含有n個記錄，則將其視為n個有序的子表，每個子表長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序表，再兩兩歸并，直到合并成一個長度為n的有序表為止，

（2）空間復雜度為O(n)；時間復雜度為O(nlog₂n)，

（3）穩定性：穩定，

7、基數排序

（1）分類：最高位優先(MSD)、最低位優先(LSD)，

（2）一趟排序需要輔助存盤空間為r，空間復雜度為O(r)；基數排序需要進行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，故基數排序時間復雜度為O(d(n+r))，與序列的初始狀態無關，

（3）穩定性：穩定，

8、內部排序的比較

9、排序小結

1）n較小，采用直接插入排序或簡單選擇排序，

2）初始狀態基本有序，采用直接插入排序或冒泡排序，

3）n較大，采用快速排序、堆排序、歸并排序，

4）n較大，關鍵字位數較少，且可分解，采用基數排序，

10、外部排序通常采用歸并排序方法，

1）外部排序所需總時間=內部排序所需時間+外存資訊讀寫時間+內部歸并所需時間

2）多路平衡歸并

（1）敗者樹：完全二叉樹且不含葉子，可采用順序存盤結構，

3）置換-選擇排序：在整個排序程序中，選擇最小（或最大）關鍵字和輸入、輸出交叉或平行進行，

4）最佳歸并樹

標籤：其他

上一篇：CF1313C2 Skyscrapers (hard version) （單調堆疊）

下一篇：資料結構（C語言版）---陣列、廣義表和壓縮存盤