数据结构之内部排序一
选择排序
选择排序的方法包含:简单选择排序、树形选择排序、堆选择排序等。我们主要讲一下最简单的选择排序:简单选择排序法。
基本思想:每一趟 (例如第 i趟,i = 0, 1, …, n-2)在后面 n-i(*1)个待排的数据元素中选出关键字最小的元素, 作为有序元素序列的第 i 个元素。
*1.有的书上或教材说是n-i+1,那是因为其他书上或者教材上都是从i = 1开始选择的,而这里是从i=0开始选择的。
简单选择排序代码
#include <stdio.h>
// 打印序列
void println(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
// 交换元素
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 选择排序算法
void SelectionSort(int array[], int len) // O(n*n)
{
int i = 0;
int j = 0;
int k = -1;
// 选择len趟
for(i=0; i<len; i++)
{
k = i; // 首先选定第i个元素是无序序列最小元素
// 遍历len-i个无序序列元素
for(j=i; j<len; j++)
{
// 与第i个元素比较,选择无序序列中最小的
if( array[j] < array[k] )
{
k = j;
}
}
// 交换数据,将其放在有序序列array[i]前面,继续比较
swap(array, i, k);
}
}
int main()
{
int array[] = {21, 25, 49, 25, 16, 8, 3, 23, 34, 12, 42, 90, 43, 64};
int len = sizeof(array) / sizeof(*array);
println(array, len);
SelectionSort(array, len);
println(array, len);
return 0;
}
i为第i趟查找,首先选定第i个元素为无序序列最小的元素,将其赋给位置k的元素,然后从j至len依次比较大小,如果发现有比第i个元素还小的元素,就更新当前位置K的数值,标记新的最小元素的位置,继续比较,直至比较len-i次,然后将最小元素与第i个位置的元素调换一下即可。重复上面的操作,直至没有最小元素为止。
插入排序
插入排序的方法包含:直接插入排序、折半插入排序、2-路插入排序、表插入排序等。我们主要讲一下最简单的插入排序:直接插入排序法。
基本思想:当插入第i (i ≥1) 个数据元素时, 前面的V[0], [1], …, V[i-1]已经排好序。这时, 用V[i]的关键字与V[i-1],V[i-2], …的关键字进行比较, 找到插入位置即将V[i]插入, 原来位置上的对象向后顺移。
插入排序看起来有点像顺序表的插入操作,只不过这里的需要比较大小后插入,而顺序表插入位置是指定的。
直接插入排序代码
#include <stdio.h>
// 打印序列
void println(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
// 插入排序算法
void InertionSort(int array[], int len) // O(n*n)
{
int i = 0;
int j = 0;
int k = -1; // 存放最小元素位置
int temp = -1; // 临时变量,用于存放比较数据
// 顺序选定第i个元素用于插入
for(i=1; i<len; i++)
{
k = i;
temp = array[k];
// 从第j个元素开始向前比较
// 如果插入的元素小于当前有序序列的元素,
// 将当前元素后移一位并且重新标记插入位置
for(j=i-1; (j>=0) && (array[j]>temp); j--)
{
array[j+1] = array[j];
k = j;
}
// 比较完毕后将选定的元素插入
array[k] = temp;
}
}
int main()
{
int array[] = {21, 25, 49, 25, 16, 8};
int len = sizeof(array) / sizeof(*array);
println(array, len);
InertionSort(array, len);
println(array, len);
return 0;
}
首先选定无序序列的第0个元素作为有序序列的首元素,然后选择后面n-1个无序序列的的第一个元素作为插入元素,与有序序列的最后一个元素进行比较,如果小于选定元素,则直接插入有序序列的后面;如果大于选定元素,将有序序列最后一个元素后移一位,将当前位置保存,然后继续与前一位元素进行比较,循环按以上方法操作,直至找到小于选定元素,将选定元素插入该位置。
冒泡排序
基本思想:设待排数据元素序列中的元素个数为 n。最多作 n-1 趟,i = 1, 2, …, n-1。在第 i 趟中从后向前,j = n-1, n-2, …, i,两两比较V[j-1]和V[j]的关键字。如果发生逆序,则交换V[j-1]和V[j]。冒泡排序代码
#include <stdio.h>
// 打印序列
void println(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
// 交换元素
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 冒泡排序算法
void BubbleSort(int array[], int len) // O(n*n)
{
int i = 0;
int j = 0;
int exchange = 1; // 定义标志位,标志有冒泡行为(交换)发生
// 查找len趟,直至无冒泡行为为止
for(i=0; (i<len) && exchange; i++)
{
// 清除冒泡标志位
exchange = 0;
// 从最后一个元素开始遍历所有的元素
for(j=len-1; j>i; j--)
{
// 比较前后元素的大小,如果当前元素比前一个元素小
// 交换这两个元素,标记冒泡行为标志位,继续与前一个元素比较
if( array[j] < array[j-1] )
{
swap(array, j, j-1);
exchange = 1;
}
}
}
}
int main()
{
int array[] = {21, 25, 49, 25, 16, 8};
int len = sizeof(array) / sizeof(*array);
println(array, len);
BubbleSort(array, len);
println(array, len);
return 0;
}
通过观察、对比上面的三种算法,发现他们的时间复杂度都是O(n^2),所以上面的排序三种算法必定不是最佳的排序方法,但这3种排序算法的排序结果都是稳定的,那么是否还有其他更高效可靠的排序方法呢?我们后面再讲。
上一篇: 《数据结构》--内部排序算法比较
下一篇: 浅析数据结构-线性表-连续存储