2 交换排序

Wu Jun 2020-02-19 12:44:57
01 数据结构与算法 > 数据结构 > 04 排序

1 冒泡排序

冒泡排序 (Bubble Sort) 一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

思路

从第 0 个到第 n 个,和相邻的元素进行相比,如果比相邻的大的话,那么就交换二者顺序,这样的话 0 到 n 范围内的最大的数就放到 n 的位置。接着下一次操作,第 0 个到第 n-1 个,将 0 到 n-1 范围内的最大值放到 n-1。重复执行,最后数组从小到大排列。

void BubbleSort(SqList *L)
{
  int i,j;
  for ( i = 1; i < L->length; i++)
  {
    for ( j = L->length - 1; j >= i; j--) /* 注意j是从后往前循环 */
    {
      if (L->r[j] > L->r[j+1]) /* 若前者大于后者(注意这里与上一算法差异) */
      {
        swap(L, j, j+1) /* 交换L->r[j]与L->r[j+1]的值 */
      }
    }
  }
}

优化

如果再一次冒泡过程中,没有发生任何数组交换,那么该数组肯定是有序的,可以提前结束冒泡。

void BubbleSort2(SqList* L)
{
  int i,j;
  Status Flag = TRUE;     /* flag用来作为标记 */
  for ( i = 1; i < L->length && flag; i++) /* 若flag为true则退出循环 */
  {
    flag == FALSE;
    for ( j = L->length - 1; j >= i; j--) /* 注意j是从后往前循环 */
    {
      if (L->r[j] > L->r[j+1]) /* 若前者大于后者(注意这里与上一算法差异) */
      {
        swap(L, j, j+1) /* 交换L->r[j]与L->r[j+1]的值 */
        flag = TRUE;    /* 如果有数据交换,则flag 为 true */
      }
    }
  }
}

复杂度分析

O(n2)

2 快速排序

快速排序(Quick Sort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

思路

最核心的思想是实现在一个范围内,以 n 为基准点,左边的数不大于基准点,右边的数不小于基准点。接下来左边的作为一个整体,同样实现上面的要求,右边的作为一个整体也实现上面的要求(左边的数不大于基准点,右边的数不小于基准点)。自顶向下执行下去,最后局部有序实现整体有序。

public static void quickSort(int array[],int start,int end){
    if(start < end){
        int n = findPoint(array,start,end);
        quickSort(array,start,n-1);
        quickSort(array,n+1,end);
    }
}

public static int findPoint(int array[],int start,int end){
    int temp = array[start];
    while(start < end){
        while(start < end && array[end] >= temp){
            end--;
        }
        if(start < end){
            array[start] = array[end];
        }
        while(start < end && array[start] <= temp){
            start++;
        }
        if(start < end){
            array[end] = array[start];
        }
    }
    array[start] = temp;
    return start;
}

复杂度分析

O(nlogn),不稳定

快速排序优化

1. 优化选取枢轴

三数取中法:取三个关键字先进行排序,将中间数作为枢轴,一般是取左端、右端和中间三个数,也可以随机选取。

对于非常大的待排序的序列,还有个九数取中法:先从数组中分三次取样,每次取三个数, 三个样品各取出中数,然后从这三个中数当中再取出 一个中数作为枢轴。

/* 优化之一: 枢轴的选择 */
int m = low + (high - low) / 2 ; /* 计算数组中间元素的下标 */
if (L->r[low] > L->r[high])
  swap(L, low, high);            /* 交换左端与右端数据,保证左端小 */
if (L->r[m] > L->r[high])
  swap(L, high, m);              /* 交换中间与右端数据,保证中间小 */
if (L->r[m] > L->r[low])
  swap(L, m, low);              /* 交换中间与左端数据,保证左端小 */
/* 此时L.r[low]已经为整个序列左中右三个关键数字的中间值 */

2. 优化不必要的交换

/* 优化之二:优化不必要的交换 */
int Partition1(SqList *L, int low, int high){
  int pivotkey;
  pivotkey = L->r[low]; /* 用于表的第一个记录作枢轴记录 */
  L->r[0] = pivotkey;   /* 将枢轴关键字备份到L->r[0] */
  while (low < high){
    while (low < high && L->r[high] >= pivotkey)
      high--;
    L->r[low] = L->r[high]; /* 采用替换而不是交换的方式进行操作 */
    while (low < high && L->r[low] <= pivotkey)
      low++;
    L->r[high] = L->r[low]; /* 采用替换而不是交换的方式进行操作 */
  }
  L->r[low] = L->r[0];     /* 将枢轴数值替换返回 L.r[low] */
  return low; /* 返回枢轴所在位置 */
}

3. 优化小数组时的排序方案

如果数组非常小,其实快速排序反而不如直接插入排序来得更好(直接插入是简单排序中性能最好的)。

/* 优化之三: 优化小数组时的排序方案 */
#define MAX_LENGTH_INSERT_SORT 7 /* 数组长度阈值 */
/* 对顺序表L中的子序列L.r[low...high]作快速排序 */
void QSort(SqList *L, int low, int high){
  int pivot;
  if (high - low > MAX_LENGTH_INSERT_SORT){
    /* 当high-low大于常数时用快速排序 */
    pivot = Partition(L, low, high);  /* 将L->r[low...high]一分为二,算出枢轴值pivot */
    QSort(L, low, pivot - 1);         /* 对低子表递归排序 */
    QSort(L, pivot + 1, high);        /* 对高子表递归排序 */
  }
  else /* 当high-low小于等于常数时用直接插入排序 */
    InsertSort(L);
}

4. 优化递归操作

/* 优化之四: 尾递归 */
/* 对顺序表L中的子序列L-r[low...high]作快速排序 */
void QSort1(SqList *L, int low, int high)
{
  int pivot;
  if ((high - low) > MAX_LENGTH_INSERT_SORT)
  {
    while (low < high)
    {
      pivot = Partition(L, low, high);  /* 将L->r[low...high]一分为二,算出枢轴值pivot */
      QSort(L, low, pivot - 1);         /* 对低子表递归排序 */
      low = pivot + 1;        /* 尾递归 */
    }
  }
  else
    InsertSort(L);
}