目录
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简单选择排序
插入排序 直接插入排序
代码如下
#define maxsize 100
int main()
{
int a[maxsize] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int n = 8;
//第一个元素a[0]可以看成一个已经排序好的子序列，因此这里可以从第二个元素开始
for (int i = 1; i < n; i++)
{
int temp = a[i];
int j;
//遇到<=就退出，可以保持排序的稳定性
for (j = i - 1; j >= 0 && a[j] > temp; j--)
{
a[j + 1] = a[j];
}
//注意，在上面的循环退出之前，j会多减一次，例如当a[0] > temp时依旧会进入循环，最终j = -1，
//因此a[j + 1]才是应该插入的位置
a[j + 1] = temp;
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
输出为：
效率分析：
若采用链表存储，插入排序时虽然元素的移动次数减少了，但是比较次数还是不变，因此平均时间复杂度依旧是(n²)
折半插入排序
#define maxsize 100
int main()
{
int a[maxsize] = { 49, 38, 65, 97, 76, 49, 13, 27, 49 };
int n = 9;
//第一个元素a[0]可以看成一个已经排序好的子序列，因此这里可以从第二个元素开始
for (int i = 1; i < n; i++)
{
int temp = a[i], j, low = 0, high = i - 1;
//二分查找，最终将会有a[high] <= temp <= a[low]，将temp插入low位置
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] > temp) high = mid - 1;
//这里需要注意，当a[mid]==temp时，为了保持算法的稳定性应该继续往右半部分查找
else low = mid + 1;
}
for (j = i - 1; j >= low; j--)
{
a[j + 1] = a[j];
}
//注意，在上面的循环退出之前，j会多减一次，例如当a[low] > temp时依旧会进入循环，最终j = low-1，
//因此a[j + 1]才是应该插入的位置
a[j + 1] = temp;
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
输出为：
效率分析：
希尔排序
对直接插入排序的一种优化算法
代码如下：
#define maxsize 100
int main()
{
int a[maxsize] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int n = 8;
for (int d = n / 2; d >= 1; d /= 2) //步长变化，逐次减半至1，当d为1时即直接插入排序
{
//当步长为d时，最多可以分为d个子表，而a[0] ~ a[d - 1]分别是这d个子表的首元素
for (int k = 0; k < d; k++)
{
//每个子表的第一个元素a[k]可以看成一个已经排序好的子序列，因此这里可以从第二个元素a[k + d]开始
for (int i = k + d; i < n; i++)
{
int temp = a[i], j;
//在访问子表中的相邻元素时要注意步长是d
for (j = i - d; j >= 0 && a[j] > a[j + d]; j -= d)
{
a[j + d] = a[j];
}
//在上面的循环退出之前，j会多减一次d，例如当子表的首元素a[k] > temp时依旧会进入循环，最终j = k-d，
//因此a[j + d]才是应该插入的位置
a[j + d] = temp;
}
}
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
输出为：
效率分析及特性：
交换排序
冒泡排序
才发现我以前一直使用的冒泡排序不知道是从哪里学来的写法，以下是吉大教材的写法，这种写法与王道书上的相反，每趟排序过程会有一个较大元素被放到数组的末尾。
#define maxsize 100
int main()
{
int a[maxsize] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int n = 8;
//根据冒泡排序的特性，n - 1趟排序之后，一定能把相对较大的n - 1个元素都排序好并放到数组的后面，
//因此循环n - 1次即可完成排序
for (int i = n - 1; i >= 1; i--)
{
bool flag = false;
for (int j = 0; j < n - 1; j++)
{
//只有在a[j] > a[j+1]时才交换，可以保证算法的稳定性
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
if (!flag) break;
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
输出为：
效率分析及特性：
快速排序
代码如下：
//一趟划分
int partition(int a[], int low, int high)
{
//这里可以视为在逻辑上移走了low位置的元素，low指向的是一个空元素
int K = a[low]; //用第一个元素作为枢轴，将待排序序列划分为左右两个部分
//何时移动low指针和high指针是有讲究的
//我们每次让指向空元素的指针固定不动，然后移动另外一个指针，再将找到的元素放到空元素位置
//因此让指向空元素的指针不动，可以视为用这个指针来记录有空元素的位置，然后可以将找到的元素放到这里来
//而第一次进入大循环前，a[low]位置是空的，因此先移动high指针，之后每次大循环同理
while (low < high)
{
//在low和high指针移动的过程中，也要随时判断两者的大小关系
while (low < high && a[high] >= K)
{
high--; //不断左移直到找到一个比枢轴小的元素
}
//这里可以视为在逻辑上移走了high位置的元素，high指向的是一个空元素
a[low] = a[high]; //把比枢轴小的元素移动到左端的空元素位置
while (low < high && a[low] <= K)
{
low++; //不断右移直到直到一个比枢轴大的元素
}
//这里可以视为在逻辑上移走了low位置的元素，low指向的是一个空元素
a[high] = a[low]; //把比枢轴大的元素移动到右端的空元素位置
}
//当最终low==high时，a[low]就是枢轴元素应该放置的地方
a[low] = K; //此时a[low]左边的元素都比K小，a[low]右边的元素都比K大，枢轴元素排序后的最终位置已经确定
return low;
}
void quicksort(int a[], int low, int high)
{
if (low < high) //递归跳出的条件
{
int index = partition(a, low, high); //划分
quicksort(a, low, index - 1); //划分左子表
quicksort(a, index + 1, high); //划分右子表
}
}
输出为：
效率分析及特性：
选择排序
简单选择排序
代码如下
#define maxsize 100
int main()
{
int a[maxsize] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int n = 8;
//每次将后面最小的元素放到前面，所以每趟形成的子序列一定是有序的，只需n - 1次循环
for (int i = 0; i < n - 1; i++)
{
int min_i = i; //记录最小元素的下标
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[min_i])
{
min_i = j;
}
}
int temp = a[min_i];
a[min_i] = a[i];
a[i] = temp;
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
return 0;
}
输出为
与直接插入排序的区别：直接插入排序的前i个元素一定是有序子序列，但是不一定是最小的i个元素。而简单选择排序的前i个元素一定是有序子序列，并且也是最小的i个元素。
与冒泡排序的区别：
1.冒泡排序是比较相邻位置的两个数，而简单选择排序是按顺序比较，找最大值或者最小值；
2.冒泡排序每一轮比较后，位置不对都需要换位置，简单选择排序每一轮比较都只需要换一次位置；
3.冒泡排序是通过数去找位置，简单选择排序是给定位置去找数；
效率分析及特性：
