ソートアルゴリズムまとめ(c言語)⑦クイックソート

クイックソート
Quick Sortは、20世紀の10大アルゴリズムの一つと呼ばれ、本格的なソートの大物が登場!
クイックソートは、交換ソートクラスに属するバブルソートのアップグレードと見なすことができます.ただし,速い列は記録の比較と移動距離を大きくし,比較と交換回数を減少させた.
高速ソートの基本思想:1回のソートによって並べ替えられるレコードを独立した2つの部分に分割し、そのうちの一部のキーワードは他の部分が記録したキーワードよりも小さい場合、この2つの部分のレコードをそれぞれソートして、シーケンス全体の秩序化の目的を達成することができる.
最適では高速配列の時間複雑度はO(nlogn)であり,最悪では時間複雑度はO(n*n)である.残念なことに、高速ソートは不安定なソートです.
ソートされるデータは、シーケンステーブルに保存されます.データの格納は0からではなく、1から開始することを選択します.コードは「大話データ構造」に参照されます.
初期設定

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 20 //       
#define N 10  //      

ちくじひょうこうぞうたい

typedef struct
{
 int data[MAXSIZE + 1];
 int len;  //       
}Sqlist;

出力順序テーブル

void Show(Sqlist L)
{
 int i;
 for (i = 1; i < L.len; ++i)
 {
  printf("%d,", L.data[i]);
 }
 printf("%d
", L.data[i]);
}

入力関数

void Input(Sqlist* lp)
{
 int d[N] = { 9, 1, 5, 8, 3, 0, 7, 4, 6, 2 };
 for (int i = 0; i < N; i++)
  lp->data[i + 1] = d[i];
 lp->len = N;
}

swap関数

void Swap(Sqlist* lp,int a, int b)
{
 int t = lp->data[a];
 lp->data[a] = lp->data[b];
 lp->data[b] = t;
}

簡単なクイックソート

int Partition(Sqlist* lp, int low, int high)
{
 int pivotkey;
 pivotkey = lp->data[low];//              
 while (low < high)//             
 {
  while (low < high && lp->data[high] >= pivotkey)
   high--;
  Swap(lp, low, high);//               
  while (low < high && lp->data[low] <= pivotkey)
   low++;
  Swap(lp, low, high);//               
 }
 return low;//        
}

void QSort(Sqlist* lp, int low, int high)
{
 int pivot;
 if (low < high)
 {
  pivot = Partition(lp, low, high);//    ，     pivot
  QSort(lp, low, pivot - 1);//        
  QSort(lp, pivot + 1, high);//        
 }
}

void QuickSort(Sqlist* lp)
{
 QSort(lp, 1, lp->len);
}

オプティマイズのクイックソート
シリーズリンク
前のソートアルゴリズム:⑥集計ソート次のソートアルゴリズム:なし