首页 > 代码库 > 排序（一）
排序（一）
（一） 插入排序（insertion sort）: 是最简单的排序算法之一，插入排序由 N - 1 趟排序组成。对于 P = 1 趟到 P = N - 1 趟，插入排序保证从位置 0 到 位置 P 的元素为已排序状态。一般方法：在第 P 趟，将位置P 上的元素向左移动到它在前P + 1 个元素中的正确位置上。（位置P 上的元素暂存于 tmp 中，而（在位置 P 之前）所有更大的元素都被向右移动一个位置。然后 tmp 被置于正确的位置上。）
void InsertSort(ElemType A[], int N) //N为数组长度
{
int j, P;
ElemType temp;
for(P = 1; P < N; P++)
{
temp = A[P];
for(j = P; j > 0 && A[j - 1] > temp; j--)
A[j] = A[j - 1];
A[j] = temp;
}
}
插入排序分析：由于嵌套循环的每一个都花费N 次迭代，因此插入排序为 O(N^2)，而且这个界是精确的，因为以反序输入可以达到该界。
（二） 希尔排序（ShellSort）：该算法是冲破二次时间屏障的第一批算法之一。它通过相聚一定间隔的元素来工作；各趟比较所用的距离随着算法的进行不断减小，直到只比相邻元素的最后一趟排序为止。
希尔排序使用一个序列 h1, h2, ... , hk ，叫做增量序列。只要 h1 = 1，任何增量序列都是可行的，不过，有些增量序列比另一些要好。在使用增量 hk的一趟排序之后，对于每一个 i 有A[i] <= A[i + hk] ；所有相隔hk 的元素都被排序。此时称文件为 hk-排序的。 希尔排序的一个重要性质是，一个 hk-排序的文件保持它的 hk-排序性。一趟 hk- 排序的作用就是对 hk 个独立的子数组执行一次插入排序的过程。
//2.希尔排序【取希尔增量：N / 2 (下取整)】
void ShellSort(ElemType A[], int N)
{
int i, j, Increment;
ElemType temp;
for(Increment = N / 2; Increment > 0; Increment /= 2)
{
for(i = Increment; i < N; i++)
{
temp = A[i];
for(j = i; j >= Increment; j -= Increment)
if(A[j - Increment] > temp)
A[j] = A[j - Increment];
else
break;
A[j] = temp;
}
}
}
使用希尔增量时希尔排序的最坏情形运行时间为 O(N^2)。其问题在于：这些增量对未必互素，因此较小的增量可能影响很小。
Hibbard提出一个稍微不同的增量序列： 1, 3, 7，... ， 2^k - 1 。使用Hibbard 增量时希尔排序的最坏情形运行时间为
O(N^(3/2)).
（三） 冒泡排序：
//3.冒泡排序(一般思维:不完全符合冒泡排序的含义)两两比较相邻元素
void BubbleSort_1(ElemType A[], int N)
{
int i, j, temp;
for(i = 0; i < N - 1; i++)
{
for(j = i + 1; j < N; j++)
{
if(A[j] < A[i])
{
temp =A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
/*
两两：是相邻的两个元素的意思
如果有n 个元素需要比较n - 1次，每一轮减少一次比较
所谓冒泡排序就是从下往上两两比较
*/
void BubbleSort_2(ElemType A[], int N)
{
int i, j, temp, flag;
flag = 1;
for(i = 0; i < N - 1 && flag; i++) //flag = 0时表示在该趟冒泡中没有元素进行交换，
//即已经为排好序的序列，可以减少比较次数
{
for(j = N - 1; j > i; j--)
{
flag = 0;
if(A[j - 1] > A[j]) //两两比较
{
temp =A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
flag = 1;
}
}
}
}
冒泡排序为O(N^2)。
全部代码：
//各种排序算法
#include<iostream>
using namespace std;
typedef int ElemType;
//1.插入排序
void InsertSort(ElemType A[], int N)
{
int j, P;
ElemType temp;
for(P = 1; P < N; P++)
{
temp = A[P];
for(j = P; j > 0 && A[j - 1] > temp; j--)
A[j] = A[j - 1];
A[j] = temp;
}
}
//2.希尔排序【取希尔增量：N / 2 (下取整)】
void ShellSort(ElemType A[], int N)
{
int i, j, Increment;
ElemType temp;
for(Increment = N / 2; Increment > 0; Increment /= 2)
{
for(i = Increment; i < N; i++)
{
temp = A[i];
for(j = i; j >= Increment; j -= Increment)
if(A[j - Increment] > temp)
A[j] = A[j - Increment];
else
break;
A[j] = temp;
}
}
}
//3.冒泡排序(一般思维:不完全符合冒泡排序的含义)两两比较相邻元素
void BubbleSort_1(ElemType A[], int N)
{
int i, j, temp;
for(i = 0; i < N - 1; i++)
{
for(j = i + 1; j < N; j++)
{
if(A[j] < A[i])
{
temp =A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
/*
两两：是相邻的两个元素的意思
如果有n 个元素需要比较n - 1次，每一轮减少一次比较
所谓冒泡排序就是从下往上两两比较
*/
void BubbleSort_2(ElemType A[], int N)
{
int i, j, temp, flag;
flag = 1;
for(i = 0; i < N - 1 && flag; i++) //flag = 0时表示在该趟冒泡中没有元素进行交换，
//即已经为排好序的序列，可以减少比较次数
{
for(j = N - 1; j > i; j--)
{
flag = 0;
if(A[j - 1] > A[j]) //两两比较
{
temp =A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
flag = 1;
}
}
}
}
int main()
{
int arr[10] = {5, 2, 8, 6, 3, 1, 7, 9, 4, 10};
//InsertSort(arr, 10);
//ShellSort(arr, 10);
BubbleSort_2(arr, 10);
for(int i = 0; i < 10; i++)
cout << arr[i] << " ";
cout << endl;
system("pause");
return 0;
}
排序（一）