(最近在做数据结构课设，刚好可以复习一下几种内部排序算法。)
排序算法分为内部排序和外部排序。如下图:
一：简单选择排序
简单选择排序顾名思义重在选择。
我们可以把一组数据中的max或者min选择出来，经过不断的选择之后使数据有序（以选择最小值为例）：
代码实现：
void selectSort(int* a, int len) {
int i, j, temp, index = 0;
int min;
for (int k = 0; k < cishu; k++)//排序进行一百次
{
for (i = 0; i < len; i++)
{
temp = a[i];
min = a[i];
for (j = i + 1; j < len; j++)
{
if (a[j] < min)
{
min = a[j];
index = j;
}
}
a[i] = min;
a[index] = temp;
}
}
}
直接插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
void InsertSort(int arr[], int n)
{
int tempVal;
for (int i = 1, j; i < n; i++)
{
tempVal = arr[i]; //保存要插入的值
for (j = i - 1; tempVal < arr[j] && j >= 0; --j) //数据往后移动，给要插入的值腾位
{
arr[j + 1] = arr[j];
}
arr[j + 1] = tempVal; //插入数据
}
}
冒泡排序
它重复地走访过要排序的元素列，依次比较两个相邻的元素，把最小的(或者最大的)往前面排。
void BubbleSort(int arr[], int n)
{
//从小到大排序 相邻来两个数比较，将大的数字往后放
for (int i = 0; i < n - 1; i++) //n-1是因为数组下标最大为n-1 要进行10轮比较
{
//n-1是因为数组下标最大为n-1 要进行10次比较，再减i是因为每最后的i个元素已经有序不需要继续排序
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1]) //两两比较，将小的数据放前面
{
swap(arr, j + 1, j); //交换arr数组arr[j+1]和arr[j]的值
}
}
}
}
//交换函数后面就不列举了，凡是swap都是下面代码实现的
void swap(int arr[], int x, int y)
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
void Quicksort(int a[], int low, int high)
{
if (low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];
while (first= key) //从右往左找一个比arr[left]小的值
{
--last;
}
a[first] = a[last];
while (first < last && a[first] <= key) //从左往右找一个比arr[left]要大的值
{
++first;
}
a[last] = a[first];
}
a[first] = key;
Quicksort(a, low, first - 1); //排左边
Quicksort(a, last + 1, high); //排右边
}
希尔排序
也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。插入排序是将未排序的数字插入到已排序数列中，而希尔排序是将一个已排序的数列插入到另一个已排序的数列中。
void ShellSort(int arr[], int n)
{
int tempVal, j;
int jump = n >> 2; //步长值
while (jump != 0)
{
for (int i = jump; i < n; i++)
{
tempVal = arr[i]; //保存待排序的第一个数，也就是待插入的数
for (j = i - jump; j >= 0 && tempVal < arr[j]; j -= jump)
{
arr[j + jump] = arr[j];
}
arr[j + jump] = tempVal;
}
jump = jump >> 1; //步长值减半
}
}
