7.11.3.1. 十大经典排序算法
排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序，而外部排序是因为排序的数据很大，一次不能容纳全部的排序记录，在排序过程中 需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等
7.11.3.1.1. 冒泡排序
7.11.3.1.1.1. 算法步骤
比较相邻的元素，如果第一个比第二个大，就交换他们两个
对每一对相邻元素做同样的工作，从开始第一对到结尾最后一对。这步做完，最后的元素会是最大的数
针对所有元素重复以上步骤，除了最后一个
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字比较
7.11.3.1.1.2. 动画演示
7.11.3.1.1.3. 参考代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int *sort(int *nums, int nums_len)
{
int *tmp_ptr = (int *)malloc(sizeof(int) * nums_len);
memcpy(tmp_ptr, nums, nums_len * sizeof(int));
for(int i = 1; i < nums_len; i++)
{
for(int j = 0; j < nums_len - i; j++)
{
int tmp = tmp_ptr[j];
if(tmp_ptr[j] > tmp_ptr[j+1])
{
tmp_ptr[j] = tmp_ptr[j+1];
tmp_ptr[j+1] = tmp;
}
}
}
return tmp_ptr;
}
int main()
{
int *dst_arr;
int test_arr[10] = {3, 5, 36, 1, 0, 9, 17, 4, 2, 8};
dst_arr = sort(test_arr, sizeof(test_arr)/sizeof(int));
for(int i = 0; i < sizeof(test_arr)/sizeof(int); i++)
printf("dst arr: %d\n", dst_arr[i]);
return 0;
}
7.11.3.1.2. 选择排序
7.11.3.1.2.1. 算法步骤
首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾
重复第二步，直到所有元素排序完毕
7.11.3.1.2.2. 动画演示
7.11.3.1.2.3. 参考代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int sort(int *nums, int nums_len)
{
int min = 0;
for(int i = 0; i < nums_len - 1; i++)
{
min = i;
int tmp = nums[min];
for(int j = i + 1; j < nums_len; j++)
{
if(nums[j] < nums[min])
min = j;
}
nums[i] = nums[min];
nums[min] = tmp;
}
for(int i = 0; i < 10; i++)
printf("dst arr: %d\n", nums[i]);
}
int main()
{
int *dst_arr;
int test_arr[10] = {3, 5, 36, 1, 0, 9, 17, 4, 2, 8};
sort(test_arr, sizeof(test_arr)/sizeof(int));
return 0;
}
7.11.3.1.3. 插入排序
7.11.3.1.3.1. 算法步骤
将排序序列第一个元素看作一个有序序列，把第二个元素到最后一个元素当成是未排序序列
从头到尾一次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与序列中的某个元素相等，则将待插入元素插到相等元素的后面)
7.11.3.1.3.2. 动画演示
7.11.3.1.3.3. 参考代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int sort(int *nums, int nums_len)
{
for(int i = 1; i < nums_len; i++)
{
int j = i;
int tmp = nums[i];
while(j > 0 && tmp < nums[j - 1])
{
nums[j] = nums[j - 1];
j--;
}
if(j != i)
nums[j] = tmp;
}
for(int i = 0; i < 10; i++)
printf("dst arr: %d\n", nums[i]);
}
int main()
{
int *dst_arr;
int test_arr[10] = {3, 5, 36, 1, 0, 9, 17, 4, 2, 8};
sort(test_arr, sizeof(test_arr)/sizeof(int));
return 0;
}
7.11.3.1.4. 希尔排序
7.11.3.1.4.1. 算法步骤
选择一个增量序列t1, t2, …. tk, 其中ti > tj, tk = 1
按增量序列个数k，对序列进行k趟排序
每趟排序，根据对应的增量ti，将待排序序列分割成若干长度为m的子序列，分别对各子表进行插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度
7.11.3.1.4.2. 动画演示
7.11.3.1.4.3. 参考代码
7.11.3.1.5. 归并排序
7.11.3.1.5.1. 算法步骤
申请空间，使其大小为两个已经已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾