1 选择法
#include <stdio.h>
#include <stdlib.h>
/*-------------------- 排序规则 --------------------
它的工作原理是每一次从待排序的数据元素中选出
最小（或最大）的一个元素，存放在序列的起始位
置，直到全部待排序的数据元素排完。
稳定性:选择排序是不稳定的排序方法 如:[5,5,3]
-------------------------------------------------*/
//选择排序(升序排列)
void selectionSort(int *array, int len)
{
int min = 0; // 指向最小的元素的位置
// 外层循环
for (int i = 0; i < len - 1; ++i)
{
min = i;
// 内存循环
for (int j = i + 1; j < len; ++j)
{
// 判断
if (array[min] > array[j])
{
// 保存最小的元素的位置
min = j;
}
}
// 判断是否需要交换
if (min != i)
{
// 找到了新的最小值
// 交换
int tmp = array[min];
array[min] = array[i];
array[i] = tmp;
}
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 12, 5, 33, 6, 10 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
selectionSort(array, len);
//遍历
printf("选择排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
2 插入排序
#include <stdio.h>
#include <stdlib.h>
/******************* 排序规则 *******************
每次处理就是将无序数列的第一个元素与有序数列
的元素从后往前逐个进行比较，找出插入位置，将
该元素插入到有序数列的合适位置中。
稳定性:插入排序是稳定的
***********************************************/
//插入排序算法(升序排列)
void insertionSort(int *array, int len)
{
int tmp = 0; // 存储基准数
int index = 0; // 坑的位置
// 遍历无序序列
for (int i = 1; i < len; ++i)
{
index = i;
tmp = array[i];
// 遍历有序序列(从后往前)
for (int j = i - 1; j >= 0; --j)
{
// 基准数根有序序列中的元素比较
if (tmp < array[j])
{
// 有序序列元素后移
array[j + 1] = array[j];
// 坑的位置
index = j;
}
else
{
break;
}
}
// 填坑
array[index] = tmp;
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 12, 5, 33, 6, 10 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (int i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
insertionSort(array, len);
//遍历
printf("插入排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
3 冒泡法
#include <stdio.h>
#include <stdlib.h>
/********************* 排序规则 *********************
冒泡排序算法的运作如下：（从后往前）
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
稳定性:冒泡排序是一种稳定排序算法
***************************************************/
//冒泡排序(升序)
void bubbleSort(int *array, int len) //O(n²)
{
#if 0
// 外层
for (int i= 0; i < len; ++i)
{
for (int j = 1; j < len - i; j++)
{
// 交换
if (array[j] < array[j - 1])
{
int tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
}
}
}
#endif
// 0: 没有排好, 1: 已经排好
int flag = 0;
for (int i = len - 1; i > 0 && flag==0; --i)
{
flag = 1; // 默认已经排好
for (int j = 0; j < i; ++j)
{
if (array[j] > array[j + 1])
{
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = 0; // 没有排好
}
}
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 11, 8, 7, 6, 3 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
bubbleSort(array, len);
//遍历
printf("冒泡排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
4 希尔排序
#include <stdio.h>
#include <stdlib.h>
/**************************** 排序规则 ****************************
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰
被分成一组，算法便终止。
稳定性: 希尔排序是非稳定排序算法。
*****************************************************************/
//希尔排序
void shellSort(int *array, int len)
{
// 步长
int gap = len;
while (gap > 1)
{
// 步长递减公式
gap = gap / 3 + 1;
// 分组, 对每一组, 进行插入排序
for (int i = 0; i < gap; ++i)
{
int tmp; // 基准数
int index; // 坑的位置
// 插入排序
// 无序序列
for (int j = i + gap; j < len; j += gap)
{
tmp = array[j];
index = j;
// 有序序列(从后往前遍历)
for (int k = j - gap; k >= 0; k -= gap)
{
if (tmp < array[k])
{
// 后移
array[k + gap] = array[k];
// 位置
index = k;
}
else
{
break;
}
}
// 填坑
array[index] = tmp;
}
}
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 12, 5, 33, 6, 10 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (int i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
shellSort(array, len);
//遍历
printf("希尔排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
5 快速排序
#include <stdio.h>
#include <stdlib.h>
//快速排序
void quickSort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r;
// 拿出第一个元素, 保存到x中,第一个位置成为一个坑
int x = s[l];
while (i < j)
{
// 从右向左找小于x的数
while (i < j && s[j] >= x)
{
//左移, 直到遇到小于等于x的数
j--;
}
if (i < j)
{
//将右侧找到的小于x的元素放入左侧坑中, 右侧出现一个坑
//左侧元素索引后移
s[i++] = s[j];
}
// 从左向右找大于等于x的数
while (i < j && s[i] < x)
{
//右移, 直到遇到大于x的数
i++;
}
if (i < j)
{
//将左侧找到的元素放入右侧坑中, 左侧出现一个坑
//右侧元素索引向前移动
s[j--] = s[i];
}
}
//此时 i=j,将保存在x中的数填入坑中
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 12, 5, 33, 6, 10 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
quickSort(array, 0, len-1);
//遍历
printf("快速排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
6 归并排序
#include <stdio.h>
#include <stdlib.h>
//快速排序
void quickSort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r;
// 拿出第一个元素, 保存到x中,第一个位置成为一个坑
int x = s[l];
while (i < j)
{
// 从右向左找小于x的数
while (i < j && s[j] >= x)
{
//左移, 直到遇到小于等于x的数
j--;
}
if (i < j)
{
//将右侧找到的小于x的元素放入左侧坑中, 右侧出现一个坑
//左侧元素索引后移
s[i++] = s[j];
}
// 从左向右找大于等于x的数
while (i < j && s[i] < x)
{
//右移, 直到遇到大于x的数
i++;
}
if (i < j)
{
//将左侧找到的元素放入右侧坑中, 左侧出现一个坑
//右侧元素索引向前移动
s[j--] = s[i];
}
}
//此时 i=j,将保存在x中的数填入坑中
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
#if 0
void main()
{
int i;
//定义整型数组
int array[] = { 12, 5, 33, 6, 10 };
//计算数组长度
int len = sizeof(array) / sizeof(int);
//遍历数组
printf("待排序数组序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
//排序
quickSort(array, 0, len-1);
//遍历
printf("快速排序之后的序列: ");
for (i = 0; i < len; ++i)
{
printf("%d\t", array[i]);
}
printf("\n");
system("pause");
}
#endif
7 算法比较
