【数据结构】冒泡、选择、插入、希尔排序的完成

1. 冒泡排序

1.1 算法思想

冒泡排序(Bubble Sort)是一种简单直观的排序算法。它重复地走过要排序的数组，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数组的工作是重复地进行直到没有再需要交换，也就是说该数组已经排序完成。

1.2 算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样就将最大的元素移动至最后，相当于这个元素已经排序完成。
3. 针对所有的元素重复以上的步骤，除了已完成排序元素。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

特别注意：如果走一轮之后，元素并没有发生任何交换则说明此时排序已经完成，可以提前结束循环。

1.3 动画演示

1.4 代码实现

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void BubbleSort(int* arr, int len)
{int flag = 0;//标记是否交换for (int i = 0; i < len - 1; i++){for (int j = 0; j < len - 1 - i; j++){if (arr[j] > arr[j + 1]){swap(&arr[j], &arr[j + 1]);flag = 1;}}if (flag == 0)//未发生交换，则排序已完成{break;}}
}

2. 选择排序

2.1 算法思想

选择排序(Selection Sort)也是一种比较直观的排序，它通过每次遍历数组选出最小或最大元素，然后与起始或者末尾位置交换，不断缩小区间，依次循环达到排序的目的。

2.2 算法步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

2.3 动画演示

2.4 代码实现

void SelectSort(int* arr, int len)
{for (int i = 0; i < len - 1; i++)//起始位置{int mini = i;for (int j = i + 1; j < len; j++)//寻找最小元素{if (arr[j] < arr[mini]){mini = j;}}swap(&arr[mini], &arr[i]);}
}

优化后：

我们可以同时选择最大与最小的元素，同时往起始与结尾位置交换。

void SelectSort(int* arr, int len)
{int begin = 0;int end = len - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[mini] > arr[i]){mini = i;}if (arr[maxi] < arr[i]){maxi = i;}}swap(&arr[mini], &arr[begin]);//如果begin与maxi重合，则需要更新maxiif (begin == maxi){maxi = mini;}swap(&arr[maxi], &arr[end]);begin++;end--;}
}

3. 插入排序

3.1 算法思想

插入排序(Insert Sort)是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它的思想类似于我们打扑克牌时的整理。

3.2 算法步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从尾到头依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
3. 依次重复1,2步骤，直至插入完成。

3.3 动画演示

3.4 代码实现

void InsertSort(int* arr, int len)
{for (int i = 0; i < len - 1; i++){int end = i;//从末尾开始插入int tmp = arr[i + 1];//保存插入元素while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;//插入}
}

4. 希尔排序

4.1 算法思想

希尔排序(Shell Sort)是插入排序的一种优化，它先通过gap将整个待排元素序列分割成若干个子序列，然后分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

希尔排序的本质就是通过gap的预排序让数据接近有序，然后再使用插入排序大大提升插入的效率。

4.2 算法步骤

1. 选取一个gap对数据进行分组，每间隔gap个元素分为一组，一共gap组。
2. 以gap为基准单位，对其进行插入排序。
3. 依次缩小gap的范围，直至gap为1，相当于进行一次正常的插入排序。

4.3 动画演示

4.4 算法实现

void ShellSort(int* arr, int len)
{int gap = len;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < len - gap; i++){int end = i;//从末尾开始插入int tmp = arr[i + gap];//保存插入元素while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tmp;//插入}}
}