数据结构的排序算法
‘壹’ 数据结构的排序算法中，哪些排序是稳定的，哪些排序是不稳定的
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法。
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
‘贰’ 数据结构C语言--三种以上的排序算法
快速排序：
void QSort(int a[], int l, int r) //单关键字交换法快排
{
int i = l, j = r, mid = (i + j) / 2; //二分[i,j]区间
while (i <= j) //让a[mid]左边都比a[mid]小，右边都比a[mid]大
{
while (a[i] < a[mid]) //找到一个元素a[i]比a[mid]小
i++;
while (a[j] > a[mid]) //找到一个元素a[j]比a[mid]大
j--;
if (i <= j) //交换a[i]和a[j]，并让指针向中间靠拢
Swap(a[i++], a[j--]);
}
if (i < r)
QSort(a, i, r); //对右区间[i,r]递归排序
if (l < j)
QSort(a, l, j); //对左区间[l,j]递归排序
}
归并排序：
void Merge(int a[], int l, int m, int r) //将a中区间[l, r]合并为有序
{
int x[101], y[101]; //循环变量
int i, j, k;
int l1 = m - l + 1, l2 = r - m; //l1表示区间[l, m]的长度，l2表示区间[m + 1, r]的长度
for (i = 1; i <= l1; i++) //将a中区间[l, m]复制到x中
{
x[i] = a[l + i - 1];
}
for (i = 1; i <= l2; i++) //将a中区间[m + 1, r]复制到y中
{
y[i] = a[m + i];
}
x[l1 + 1] = MaxInt; //设置一个很大的数作为结束标志
y[l2 + 1] = MaxInt;
i = 1;
j = 1;
for (k = l; k <= r; k++) //将两个区间合并成为一个有序区间
{
if (x[i] <= y[j])
{
a[k] = x[i++];
}
else
{
a[k] = y[j++];
}
}
}
void MergeSort(int a[], int l, int r) //对a数组的[l, r]区间排序
{
int m;
if (l < r)
{
m = (l + r) / 2; //二分区间[l, r]
MergeSort(a, l, m); //递归二分区间[l, m]
MergeSort(a, m + 1, r); //递归二分区间[m + 1, r]
Merge(a, l, m, r); //合并区间[l, m]和[m + 1, r]
}
}
二叉排序树排序：
struct BinaryTree //二叉树结构
{
int data, p, l, r; //data数值域，p父节点编号，l左儿子编号，r右儿子编号
};
int root = 0;
void Init(BinaryTree a[], int &n) //读入数据域，并初始化树
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].data;
a[i].p = a[i].l = a[i].r = -1;
}
}
void Insert(BinaryTree a[], int i) //在二叉查找树中插入编号为 i 的节点
{
int parent = -1, x = a[1].p; //parent 始终指向 x 的父节点编号
while (x != -1) //向下搜索，直到找到最下一层
{
parent = x;
if (a[i].data < a[x].data)
x = a[x].l;
else
x = a[x].r;
}
a[i].p = parent; //把第 i 号节点的父亲指向parent
if (parent != -1) //判断树是否为空
{
if (a[i].data < a[parent].data) //向父节点插入儿子
a[parent].l = i;
else
a[parent].r = i;
}
else //为空就以 i 节点为根节点
a[root].p = i;
}
void BuildTree(BinaryTree a[], int n) //建立二叉查找树
{
root = 1;
for (int i = 1; i <= n; i++) //依次插入 n 个节点到二叉查找树
{
Insert(a, i);
}
a[root].p = -1;
}
void Sort(BinaryTree a[], int i) //中序遍历输出
{
if (a[i].l > -1) //递归遍历左儿子
Sort(a, a[i].l);
cout << a[i].data << " "; //输出节点
if (a[i].r > -1) //递归遍历右儿子
Sort(a, a[i].r);
}
堆排序：
void Heap(int a[], int n, int p) //维护最大（最小）堆，维护以P为根的堆
{
int l = p * 2, r = l + 1, t = p; //左儿子编号为2P，右儿子为2P+1，初始化根节点P为最大
if ((l <= n) && (a[l] > a[p])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = l;
if ((r <= n) && (a[r] > a[t])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = r;
if (p != t) //如果根节点不是最大，和最大的交换，再递归维护堆
{
Swap(a[p], a[t]);
Heap(a, n, t);
}
}
void HeapSort(int a[], int n)
{
int i;
for (i = n / 2; i >= 1; i--) //n / 2开始必然是根节点，依次调用Heap，建立一个最大堆
Heap(a, n, i);
for (i = n; i >= 2; i--) //每次将堆顶和当前堆最后一个节点(i)交换，然后将[1, i - 1]重新堆化
{
Swap(a[i], a[1]);
Heap(a, i - 1, 1);
}
}
插入排序：
void InsertionSort(int a[], int l, int r) //对区间[l, r]执行插入排序
{
int i, j, t;
for (i = l + 1; i <= r; i++)
{
j = i - 1;
t = a[i];
while ((j >= l) && (a[j] > t)) //后移操作，并找到正确的位置
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}
以上所有的Swap函数的意思都是交换两个变量。
‘叁’ 数据结构中比较各种排序算法 求详解 ，，，，，，，，，，
排序算法包括：插入排序、交换排序、选择排序以及合并排序。
其中插入排序包括直接插入排序和Shell排序，交换排序包括冒泡排序和分化交换排序，选择排序包括直接选择排序和堆排序。
这些排序算法中，直接插入排序、冒泡排序和直接选择排序这三种排序的算法平均时间复杂度是O(n的平方)；分化交换排序、堆排序和合并排序这三种排序的算法平均时间复杂度是
‘肆’ 数据结构中有哪些基本算法
数据结构中最基本的算法有：查找、排序、快速排序，堆排序，归并排序，，二分搜索算法
等等。
1、用的最多也是最简单的数据结构是线性表。
2、有前途的又难数据结构是图 。
3、常用的80％算法是排序和查找。
‘伍’ 数据结构的排序算法中，哪些排序是稳定的，哪些排序是不稳定的
一、稳定排序算法
1、冒泡排序
2、鸡尾酒排序
3、插入排序
4、桶排序
5、计数排序
6、合并排序
7、基数排序
8、二叉排序树排序
二、不稳定排序算法
1、选择排序
2、希尔排序
3、组合排序
4、堆排序
5、平滑排序
6、快速排序
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。
做这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
(5)数据结构的排序算法扩展阅读：
排序算法的分类：
1、通过时间复杂度分类
计算的复杂度（最差、平均、和最好性能），依据列表(list)的大小(n)。
一般而言，好的性能是 O(nlogn)，且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。
而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。
2、通过空间复杂度分类
存储器使用量（空间复杂度）（以及其他电脑资源的使用）
3、通过稳定性分类
稳定的排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。
‘陆’ 数据结构的排序方法有哪些
冒泡排序，快速排序，堆排序。
‘柒’ 数据结构排序算法有哪些常用的
最常用的是快速排序，基数排序，计数排序，归并排序，堆排序，（偶尔还有插入排序）
都有各自的应用，快排就是单纯的快，但是特殊数据下复杂度会退化
基数排序可以配合一些特定的算法，譬如后缀数组的构建
计数排序简单且常用，通常排序值域小但是数据量大的情况
归并直接用来排序并不多，但是可以用来求解一些其他问题，本身的思想也非常重要，有很多拓展的算法（不是排序算法）
堆排序胜在稳定，不论数据如何最坏都是O(nlogn)，一般情况比快速排序慢些，但是极端情况下表现十分优秀，常用来配合快速排序，优化其稳定性
插入排序适合极少量数据的排序（几个到十几个），速度要比这些高级算法快一些