10.21 冒泡排序

借助一道题来练习排序算法：

在这里插入图片描述

（从小到大）冒泡排序是每次比较相邻的两个元素大小，如果第一个比第二个大，交换位置，直到末尾。每次到达末尾之后当前元素作为新的末尾进行下一次冒泡。直到再也没有需要交换的。

图解：

在这里插入图片描述

算法实现：

/** * Note: The returned array must be malloced, assume caller calls free(). */void Swap(int *a, int *b) {
       int k;    k = *a;    *a = *b;    *b = k;}void BubbleSort(int *nums, int numsSize) {
       int i, j;    int last_pos, is_sorted = 1;    last_pos = numsSize-1;    /* 冒泡排序 */    for (i = last_pos; i > 0; i--) {
     //以上次结束的位置为准        is_sorted = 1; //每次开始前先假定有序        for (j = 0; j < i; j++) {
               if (nums[j] > nums[j + 1]) {
                    Swap(&nums[j], &nums[j + 1]);                                last_pos = j;  //记录当前交换位置                is_sorted = 0;             }        }        if (1 == is_sorted) break;//数组本来就有序，返回    }}int* sortArray(int* nums, int numsSize, int* returnSize){
       int last_pos, is_sorted = 1;    int *new = (int*)malloc(sizeof(int) * numsSize);    *returnSize = numsSize;    if (1 == numsSize) return nums;    BubbleSort(nums, numsSize); //冒泡排序    new = nums;      //栈里面处理更快，所以等排序完成之后再输出    return new;}

优化：

基于最基本的冒泡排序，做了以下几点优化：

若数组本来就有序或者排序几次后有序，直接输出。在每次循环开始的时候is_sorted = 1假定数组有序，根据is_sorted来判断，若发生交换，则代表无序；若一次循环过后无交换则1 == is_sorted直接输出原数组

若数组局部有序，则在下一次循环的时候无需对有序的部分再次进行排序，决定循环长度的是外层循环，所以外层循环的长度由上一次最后交换为位置决定：for (i = last_pos; i > 0; i--)，其中last_pos记录的是上一次循环最后的交换位置，在内存循环中更新

10.22 选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧，在链表情况下使用比较稳定。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

分为两部分，前半部分是已排序部分，后半部分是未排序部分，后面逐步将未排序部分的最小值找出依次放在已排序后面，作为已排序部分新的最大值。

选择排序的特点：

①、运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息；

②、数据移动是最小的。每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。（其他大部分排序算法的增长数量级都是线性对数或是平方级别的）

图解：

基础算法实现：

void SelectionSort(int *nums, int numsSize) {
       int i, j, min;         for (i = 0; i < numsSize - 1; i++) {
        //外层循环决定有序部分的长度        min = i;        for (j = i + 1; j < numsSize; j++) {
    //处理未排序部分            if (nums[j] < nums[min]) {
                   min = j;            }                   }        Swap(&nums[min], &nums[i]);    }}

10.23 插入排序

插入排序和选择排序实现有些类似，都是分为已排序部分和未排序部分来看的，选择排序是每次选出未排序部分的最小值作为已排序部分的最大值。插入排序是在未排序部分中，依次排序，每次看一个元素，将此元素与已排序部分比较，直到找到在已排序部分中的位置。

插入排序，可以理解为插队式排序，从最后面依次寻找可插队的对象，对于比自己大的值，不敢在它面前插队，一旦遇到比自己小的值，就立刻插队。

图解：

在这里插入图片描述

算法实现：

/* 插入排序 */void InsertSort(int *num, int numsSize){
       int i, j, key;    for (i = 1; i < numsSize; i++) {
     //i表示 有序范围        key = num[i];        j = i - 1;        while ( (j >= 0)&& (num[j] > key)) {
     //顺序也有要求，从左到右先为1就直接退出            num[j + 1] = num[j];              //排挤元素            j--;        }        num[j + 1] = key;   //插入到适合的位置    }}

要注意，while判断中(j >= 0)的优先级要比后面的高，不然可能造成内存泄漏问题！！！

插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，但是插入排序在数组基本有序的情况下效率是很高的。

10.24 希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

希尔排序是插入排序的高阶优化。利用的就是插入排序在数组基本有序的情况下效率很高的优点，先对数组进行大块的插入排序，使数组基本有序，再对基本有序的数组使用插入排序。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

通俗来讲，希尔排序就是一层一层插入排序叠加起来的。

图示：

在这里插入图片描述

算法实现：

/* 希尔排序 */void ShellSort(int *num, int numsSize){
       int gap, i, j, key;    for (gap = numsSize / 2; gap > 0; gap /= 2) {
     //分组  gap是分组的个数        for (i = gap; i < numsSize; i++) {
            //每个分组内进行插入排序            /* 插入排序 */            key = num[i];            j = i - gap;            while ((j >= 0) && (num[j] > key)) {
                   num[j + gap] = num[j];                j -= gap;            }            num[j + gap] = key;        }    }}

还有一种基于优化插入方法的希尔排序：

/* 基于优化插入的 希尔排序 */void shellsort3(int a[], int n){
   	int i, j, gap; 	for (gap = n / 2; gap > 0; gap /= 2)		for (i = gap; i < n; i++)			for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)				Swap(&a[j], &a[j + gap]);}