1. 简介
排序算法是计算机程序中最常用的基本操作之一。排序算法按照某种顺序重新排列一组数据集合。排序技术不仅常用于数据存储,还可以作为计算其他算法的一个子程序。本文将介绍排序算法中的两种基本算法:选择排序和冒泡排序。同时会使用程序示例展示它们的用法和实现原理。
2. 选择排序
2.1 定义
在桶排序、计数排序和基数排序中,选出最小的元素是一个重要的操作。选择排序就是在这个基础之上的一种算法。其具体实现为:首先在未排序列表中找到最小元素,然后将其存放到排序列表的起始位置;接着再从剩余未排序的元素中继续寻找最小元素方法到已排序列表的末尾。以此类推,直到所有元素都排列完成。
2.2 过程
下面我们用程序示例来演示选择排序的过程。假设我们的需求是将一个无序数组从小到大排序。那么首先我们需要找到这个数列中最小的数,并把它放在首位;然后再从剩下未排序的数列中找到最小值,放到已排序数组的最后一位。直至所有数排序完成。
public static void selectSort(int[] array) {
//array为待排序数组
int n = array.length;
for (int i = 0; i < n; i++) {
//初始化最小元素下标为i
int minIndex = i;
//遍历未排序部分,寻找最小元素,与已排序部分相连
for (int j = i + 1; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
//将最小元素与当前的起始元素交换位置
swap(array, i, minIndex);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
当我们调用selectSort()函数时,数组会被遍历,最小的数值会被找出并交换它在数组中的位置,当我们再次从剩下的数值中寻找时,数组会被分为已经排序过的部分和尚未排序的部分,直至数组排序完成。
2.3 示例
假设我们有以下未排序的数组:[13, 45, 2, 67, 11, 5]。那么我们来分步演示一下使用选择排序法排序的过程:
步骤1:选择最小的元素并将其与首位交换 [2, 45, 13, 67, 11, 5]
步骤2:从剩下未排序的元素中,寻找最小的元素并与第二个元素交换位置 [2, 5, 13, 67, 11, 45]
步骤3:重复步骤2,直到所有元素都被排序完成 [2, 5, 11, 13, 45, 67]
3. 冒泡排序
3.1 定义
冒泡排序是一中可以通过交换相邻元素的方式,让每一趟只排好一个数字的排序算法。通过对待排序序列从前向后,依次比较相邻的两个元素,将较大的元素交换至右侧,一趟排序完成后,我们会发现此序列中最大的元素已沉到序列底部,下一趟排序时,只需将未排序列中最后一个元素之前的部分重复前面步骤进行对比交换即可,直到排序完成。
3.2 过程
下面我们使用程序示例演示一下冒泡排序的过程。假设我们的需求是将一个无序数组从小到大排序。那么首先我们需要将第一个数和第二个数进行对比,如果第一个数比第二个数大,则交换两个数的位置;接着比较第二个数和第三个数,如果第二个数比第三个数大,则交换它们的位置。直到所有数排列完成。
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
当我们调用bubbleSort()函数时,从第一个元素开始比较,每一趟对比都会留下一个较大的元素,直到最后一趟会有一个最大的元素位于数组的最后一个位置,从而完成数组排序。下图将演示这个过程。
通过上述过程,我们可以看出,选择排序和冒泡排序在实现过程上有相似性,但是它们的实现方式和效率不同。选择排序的时间复杂度是O(n2),而冒泡排序的时间复杂度也是O(n2)。但是相比选择排序,冒泡排序需要更多的交换次数,所以冒泡排序的速度较慢。
4. 总结
本文主要介绍了排序算法中的两种基本算法:选择排序和冒泡排序。虽然它们的实现过程和时间复杂度都相似,但是各自的效率不同。选择排序的交换次数少,往往在一些特殊场景中有意想不到的表现。而冒泡排序具有可读性高、代码简单等特点,但是由于它需要更多的交换次数,所以在大规模数据排序时会显得比较低效。在实际应用中,我们可以根据具体需求选择适合的排序算法。