Java重点之基于比较的七大排序
在计算机科学中,排序是一种重要的基本操作,将一组元素按照一定的规则进行排列。排序算法的效率直接影响着程序的执行效率,因此需要掌握各种排序算法的实现方法及其优缺点。基于比较的排序算法,是按照元素之间的大小关系进行比较和交换,常见的基于比较的排序算法有冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序和希尔排序。
冒泡排序
冒泡排序的基本思想是把相邻的元素进行比较和交换,大的元素往后移。具体来说,每一轮排序都将当前所有未定位置的元素中最大的元素放到数组的最后面。
算法步骤:
1. 从前向后扫描n个元素
2. 如果相邻两个元素a[i]和a[i+1]逆序,交换它们的位置
3. 重复步骤1和2直到没有未排序的元素
示例:
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
快速排序
快速排序是一种常用的排序算法,采用分治思想,将待排序列分为两个子序列,一边序列小于另一边序列,递归地排序子序列,最终实现整个序列的有序排列。
算法步骤:
1. 从待排序列中任选一个元素作为枢轴,通常选择第一个元素
2. 扫描待排序列,将小于枢轴的元素移到枢轴之前,大于枢轴的元素移到枢轴之后
3. 递归地对枢轴之前和之后的子序列进行排序
示例:
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int pivot = partition(array, left, right);
quickSort(array, left, pivot-1);
quickSort(array, pivot+1, right);
}
}
public static int partition(int[] array, int left, int right) {
int pivot = array[left];
int i = left, j = right;
while (i < j) {
while (i < j && array[j] >= pivot) j--;
if (i < j) array[i++] = array[j];
while (i < j && array[i] <= pivot) i++;
if (i < j) array[j--] = array[i];
}
array[i] = pivot;
return i;
}
总之,对于基于比较的排序算法,不同排序算法的实现细节、效率及其特点是不一样的,在实际编写程序中应该灵活选择算法,并特别注意算法的性能问题,避免得不偿失的效果,提高程序的执行效率。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java重点之基于比较的七大排序 - Python技术站