数据结构与算法分析 — 排序算法
概述 排序算法
冒泡排序 插入排序 希尔排序 堆排序 归并排序 快速排序
概述
后面的排序算法中,假设待排元素是整数,且按照非递减排序. 后面程序中待排元素统一定义如下:
typedef int ElementType;
冒泡排序(Bubble Sort)
它重复地遍历待排序的序列,一次比较相连的两个元素,如果他们的顺序错误就把他们交换过来.每一次遍历,都使最后的元素是前面的序列中最大的.遍历序列的工作是重复地进行直到没有再需要交换.
冒泡排序程序
void Bubble_Sort(
int A[],
int N)
{
int i,j,tmp;
int flag;
for ( i = N-
1; i >
0; i-- ) {
flag =
1;
for ( j =
0; j < i; j++ )
if ( A[j] > A[j+
1] ) {
tmp = A[j];
A[j] = A[j+
1];
A[j+
1] = tmp;
flag =
0;
}
if ( flag )
break;
}
}
插入排序(Insertion Sort)
插入排序由
N−1
趟排序组成.对于
P=k
趟,插入排序保证从位置
0
到位置P上的元素为已排序状态.直到
P=N−1
趟结束.
插入排序程序
void Insertion_Sort(ElementType A[],
int N)
{
int i,j;
ElementType X;
for ( i =
1; i < N; i++ ) {
X = A[i];
for ( j = i; j >
0 && A[j-
1] > X; j-- )
A[j] = A[j-
1];
A[j] = X;
}
}
希尔排序(Shell Sort)
