在数据结构中我们常见的排序算法有：直接插入排序、希尔排序、选择排序、堆排序、交换排序（冒泡排序）、快速排序、归并排序，接下来我给大家分享一下我在写这些代码时的想法（从小到大，从左到右），以及各个排序的比较
首先我们得写一个交换函数，因为后面基本每个排序都有使用。
void Swap(int *x, int *y)//交换函数
{
int tmp = *x;
*x = *y;
*y = tmp;
}一、直接插入排序
1、思路
插入排序顾名思义就是把数据一个一个插入到有序序列中。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
第一次插入【21】25 49 25* 16 8
第二次插入【21 25】49 25* 16 8
第三次插入【21 25 49】25* 16 8
第四次插入【21 25 25* 49】16 8
第五次插入【16 21 25 25* 49】8
第六次插入【8 16 21 25 25* 49】
3、源代码
void InsertSort(int *a, int n)//插入排序
{
assert(a);
for (int i = 1; i < n; i++)
{
int j = i - 1;
while (j >= 0)
{
if (a[j + 1] < a[j])
{
Swap(&a[j], &a[j + 1]);
j--;
}
else
break;
}
}
}二、希尔排序
1、思路
希尔排序其实就是插入排序的优化，因为当原数组时倒序时，每进行一次插入都要将前面的元素向后移动，所以我们可以进行预排序将数组每相隔gap个数进行排序。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
gap=3：21 16 8 25* 25 49
gap=1：8 16 21 25* 25 49
3、源代码
void ShellSort(int *a, int n)//希尔排序
{
assert(a);
for (int gap = n / 2; gap > 0; gap /= 2)//gap为相隔个数当相隔为1时就是直接插入排序
{
for (int i = gap; i < n; i++)
{
int j = i;
while (j - gap >= 0)
{
if (a[j] < a[j - gap])
Swap(&a[j], &a[j - gap]);
j -= gap;
}
}
}
}三、选择排序
1、思路
选择排序也顾名思义，就是选出来一个最大和最小的的元素，一个一个排下去。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
第一次排序8 【25 21 25*16】49
第二次排序8 16【21 25*】25 49
第三次排序8 16 21 25* 25 49
3、源代码
void SelectSort(int *a, int n)//选择排序
{
assert(a);
int min = 0, max = 0, left = 0, right = n-1;
while (left<=right)
{
for (int i = left; i<=right;i++)//选出最大数和最小数
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
Swap(&a[min], &a[left]);
if (max == left)//当最大数在左边时，上一次的交换以将最大数换走，所以改变最大数下标
max = min;
Swap(&a[max], &a[right]);
left++;
right--;
}
}四、堆排序
1、思路
将一位数组按完全二叉树的顺序存储方式存储，而且父亲结点元素值大于它的孩子结点值，升序建大堆，降序建小堆。
2、例：数组 { 21,
25, 49,
25*, 16, 8 }
第一次向上调整21 25 49 25* 16 8
第二次向上调整49 25 21 25* 16 8
第一次向下调整49 25 21 25* 16 8交换后8 25 21 25* 16【49】
第二次向下调整25 25* 21 8 16【49】交换后16 25* 21 8【25 49】
第三次向下调整25* 16 21 8【25 49】交换后8 16 21【25* 25 49】
第四次向下调整21 16 8【25* 25 49】交换后8 16【21 25* 25 49】
第五次向下调整16 8【21 25* 25 49】交换后8【16 21 25* 25 49】
3、源代码
void Heap(int *a, int root)
{
assert(a);
for (int parent = (root - 1) / 2; parent >= 0;parent--)
{
int child = 2 * parent + 1;
if (child != root&&a[child] < a[child + 1])//选出孩子中最大元素
++child;
if (a[parent] < a[child])
Swap(&a[parent], &a[child]);
}
}
void HeapSort(int *a, int n)//堆排序，建大堆
{
assert(a);
Heap(a, n);//向上调堆
while (n>1)
{
for (int parent = 0; parent <= (n - 1) / 2; parent++)//向下调堆
{
int child = parent * 2 + 1;
if (child < (n - 1) && a[child] < a[child + 1])
++child;
if (child < n&&a[parent] < a[child])
Swap(&a[parent], &a[child]);
}
Swap(&a[0], &a[n - 1]);//将最后一个元素和开始元素奇交换
n--;
}
}五、交换排序（冒泡排序）
1、思路
每次交换将最大的值放置右端，然后从右向左排下去。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
第一次交换21 25 25* 16 8【49】
第二次交换21 25 16 8【25* 49】
第三次交换21 16 8【25 25* 49】
第四次交换16 8【21 25 25* 49】
第五次交换8【16 21 25 25* 49】
第六次交换【8 16 21 25 25* 49】
3、源代码
void BubbleSort(int *a, int n)//冒泡排序
{
assert(a);
for (int i = 0; i < n; i++)
{
for (int j = 0; j + 1 < n - i; j++)
{
if (a[j]>a[j + 1])
Swap(&a[j], &a[j + 1]);
}
}
}六、快速排序
1、思路
在数组中选出一个标记值，比它大的排右边，比他小的排左边，排完后的位置就是有序后的位置。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
第一次快速排序8【25 49 25* 16 21】
第二次快速排序8【【16】21【25* 49 25】】
第三次快速排序8【【16】21【【25*】 25 【49】】】
3、源代码
int Quick(int *a, int left, int right)
{
assert(a);
while (left < right)
{
for (; left<right; left++)//找到大的进行交换
{
if (a[left] > a[right])
{
Swap(&a[left], &a[right]);
right--;
break;
}
}
for (; left < right; right--)//找到小的进行交换
{
if (a[right] < a[left])
{
Swap(&a[left], &a[right]);
left++;
break;
}
}
}
return right;//返回标记值的有序下标
}
void QuickSort(int *a, int left, int right)//快速排序
{
assert(a);
if (left < right)
{
int div = Quick(a, left, right);//区分左右区间
QuickSort(a, left, div - 1);//处理比标记值小的
QuickSort(a, div + 1, right);//处理比标记值大的
}
}七、归并排序
1、思路
将数组每次平均划分下去，最后有序进行归并。
2、例：数组a[] = { 21, 25, 49, 25*, 16, 8 }
第一次划分【21 25 49】【25* 16 8】
第二次划分【【21】【25 49】】【【25*】【16 8】】
第三次划分【【21】【【25】【49】】】【【25*】【【16】【8】】】
第一次归并【【21】【25 49】】【【25*】【8 16】】
第二次归并【21 25 49】【8 16 25*】
第三次归并8 16 21 25 25* 49
3、源代码
void Merge(int *a, int left, int div, int right)
{
assert(a);
int llen = div - left + 1;
int rlen = right - div;
int i = 0, j = 0, x = 0;
int *l, *r;
l = (int*)malloc(sizeof(int)*llen);
r = (int*)malloc(sizeof(int)*rlen);
for (i = 0; i < llen; i++)
l[i] = a[left + i];
for (i = 0; i < rlen; i++)
r[i] = a[div + i + 1];
i = 0;
j = 0;
while (i < llen && j < rlen)
{
if (l[i] <= r[j])
a[left + x++] = l[i++];
else
a[left + x++] = r[j++];
}
while (i < llen)
a[left + x++] = l[i++];
while (j < rlen)
a[left + x++] = r[j++];
}
void MergeSort(int *a, int left, int right)//归并排序
{
assert(a);
int div = left + ((right - left) >> 1);
if (left < right)
{
MergeSort(a, left, div);
MergeSort(a, div + 1, right);
Merge(a, left, div, right);
}
}八、测试代码
int main()
{
int a[] = { 21, 25, 49, 25, 16, 8 };
//int a[] = { 9, 17, 65, 23, 45, 78, 87, 53, 31 };
//InsertSort(a, sizeof(a) / sizeof(a[0]));
//ShellSort(a, sizeof(a) / sizeof(a[0]));
//SelectSort(a, sizeof(a) / sizeof(a[0]));
//HeapSort(a, sizeof(a) / sizeof(a[0]));
//BubbleSort(a, sizeof(a) / sizeof(a[0]));
//QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
MergeSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}九、各个排序比较