排序sort

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:

在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。

当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。

在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。

排序算法性能评价

   1 typedef int key_type;
   2 typedef struct{ 
   3     key_type key;
   4     info_type otherinfo;
   5 }record_type;
   6 typedef record_type elem_type;
   7 typedef struct  {
   8     elem_type  elem[MAXSIZE];
   9     int size;
  10 }seq_list;

1. 插入排序

1.1. 直接插入排序

假设待排序的记录存放在数组R[0..n-1]中。初始时,R[0]自成1个有序区,无序区为R[1..n-1]。从i=1起直至i=n-1为止,依次将R[i]插入当前的有序区R[0..i-1]中,生成含n个记录的有序区。

   1 void insert_sort(seq_list *r) {
   2     int i, j;
   3     for(i = 1; i<=r->size; i++) {
   4         elem_type e = r->elem[i];
   5         for( j = i-1; j >= 0; j--) {
   6             if(r->elem[j].key < e)
   7                 break;
   8             r->elem[j+1] = r->elem[j]; 
   9         }
  10         r->elem[j+1] = e;
  11     }
  12 }

例:49,38,65,97,76,13,27,49

时间复杂度:最好情况(正序)O(n),最坏情况(逆序)O(n2),平均情况O(n2)

空间复杂度O(1)

稳定性:稳定

1.2. 希尔排序

2. 交换排序

基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。

2.1. 冒泡排序

将被排序的记录数组R[0..n-1]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组 R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

例:49 38 65 97 76 13 27

   1 void swap(seq_list *r, int i, int j) {
   2    elem_type t = r->elem[i];
   3    r->elem[i] = r->elem[j];
   4    r->elem[j] = t; 
   5 }
   6 
   7 void bubble_sort(seq_list *r) { 
   8     int i, j;
   9     int swap_flag;
  10     for(i = r->size; i > 1; i--) {
  11         swap_flag = 0;
  12         for(j = 0; j < i-1; j++)
  13             if(r->elem[j].key > r->elem[j+1].key){
  14                 swap(r, j, j+1);
  15                 swap_flag = 1;
  16             }
  17         if(swap_flag == 0)
  18             return;
  19     }
  20 }

时间复杂度:最好情况(正序)O(n),最坏情况逆序O(n2),平均情况O(n2)

空间复杂度:O(1)

稳定性:稳定

2.2. 快速排序

   1 void QuickSort(seq_list *s, int left, int right) {
   2    if(left < right) {
   3       int i = left + 1;
   4       int j = right;
   5       while(i <= j) {
   6          while(i <= j && s->elem[left].key <= s->elem[j].key) j--;
   7          while(i <= j && s->elem[i].key <= s->elem[left].key) i++;
   8          if(i<j)
   9             swap(s, i, j);
  10       }
  11       swap(s, left, j);
  12       QuickSort(s, left, j-1);
  13       QuickSort(s, j+1, right);
  14    }
  15 }

3. 选择排序

选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。

3.1. 简单选择排序

   1 void SelectSort(seq_list *r) {
   2    int i, j, k;
   3    for(i=0; i < r->size-1; i++){
   4       k = i;
   5       for(j = i+1; j<r->size;j++)
   6          if(r->elem[j].key < r->elem[k].key)
   7             k = j; 
   8       if(k!=i) { 
   9          elem_type temp = r->elem[i];
  10          r->elem[i] = r->elem[k];
  11          r->elem[k] = temp; 
  12       }
  13    } 
  14 }

例子:49、38、65、97、76、13、27

时间复杂度:比较次数0(n2);移动次数最好情况0,最坏情况3(n-1);平均时间复杂度0(n2)。

空间复杂度:O(1)

稳定性:不稳定

3.2. 堆排序

   1 void shift(elem_type elem[], int start, int end) {
   2    elem_type root = elem[start];
   3    while( 1 ) {
   4       int child = 2 * (start+1) - 1;
   5       if(child + 1 <= end && elem[child].key < elem[child+1].key) 
   6          child ++;
   7       if(child > end || root.key >= elem[child].key)
   8          break;
   9       elem[start] = elem[child];
  10       start = child;
  11    }
  12    elem[start] = root;
  13 }
  14 
  15 void heapsort(seq_list *r) {
  16    int i;
  17    for( i = r->size/2; i >= 0; i--) {
  18       shift(r->elem, i, r->size-1);
  19    }
  20    for( i = r->size-1; i >= 1; i--) {
  21       swap(r, 0, i);
  22       shift(r->elem, 0, i-1);
  23    }
  24 }

4. 归并排序

   1 void merge(seq_list *s, int left, int mid, int right) {
   2    int i = left, j = mid, k = 0;
   3    seq_list r;
   4    while(i < mid && j <= right) {
   5       if(s->elem[i].key <= s->elem[j].key) 
   6          r->elem[k++] = s->elem[i++];
   7       else
   8          r->elem[k++] = s->elem[j++];
   9    }
  10    while(i < mid) 
  11       r->elem[k++] = s->elem[i++];
  12    while(j <= right)
  13       r->elem[k++] = s->elem[j++];
  14    r->size = k;
  15    for(k = 0; k < r->size; k++) 
  16       s->elem[left+k] = r->elem[k];
  17 }
  18 
  19 void merge_sort(seq_list *s, int left, int right) {
  20    int mid = (left+right)/2;
  21    if(left >= right) return;
  22    merge_sort(s, left, mid);
  23    merge_sort(s, mid, right);
  24    merge(s, left, mid, right);
  25 }

排序 (last edited 2008-02-23 15:35:54 by localhost)

ch3n2k.com | Copyright (c) 2004-2022 czk.