常见排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了常见排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3866字,纯文字阅读大概需要6分钟。
内容图文
![常见排序算法](/upload/InfoBanner/zyjiaocheng/593/e05196ce3d7b45ad899598fa4536d8b7.jpg)
这些基础的算法真是容易忘,一段时间不写细节就不会处理了。在此记录一下。
1、初级的桶排序
如需要对10以内的数进行排序,可以先初始化一个长度为10的数组。然后遍历,遍历到哪个数就将数组对应的下标加1,如遍历到3,则a[3]++。整个遍历结束后,再通过输出数组即可得到有序数据。需要注意的是,a[i]是多少则需要打印多少次。
这种算法相当于是用下标记录数据,用值记录次数。
该算法的优点是快速,其时间复杂度是O(n)。但是该算法的缺点是占用过多的空间,如果需要对10000个数排序,那么需要申请长度10000数组来存储,相当于用空间换时间。
参考代码如下:
/**
* 简单的桶排序(实际的桶排序要比这个复杂)
* @param a 待排序的数组
*/
public static void bucketSort(int[] a) {
// 先定义桶
int[] tong = new int[10]; // 假设a数组存放的是10以内的数据,故需要定义10个桶
for (int i = 0; i < tong.length; i++) {
tong[i] = 0; // 初始化桶中的每一位数 (假设待排序的数中不存在-1)
}
// 遍历待排数据,将数据放入到相应的桶中
for (int i = 0; i < a.length; i++) {
tong[a[i]]++;
}
// 输出桶中的数据,即已经排序好的数据
for (int i = 0; i < tong.length; i++) {
// 只打印存放了数据的桶
if (tong[i] != 0) {
for (int j = 0; j < tong[i]; j++) {
// 在某个桶的位置上重复了几次,那么就打印多少次
System.out.print(i + ",");
}
}
}
}
2、冒泡排序
冒泡排序的思想是通过依次比较相邻的两个数的,如果顺序不对,则进行调换。在每一真趟的的冒泡的过程中,只能将一个数归位。在对n个数排序中,只需将n-1归位即可。故排序n个的数只需要n-1趟。该算法的优点是理解及实现难度不在,但是时间复杂度为O(n2)。
参考代码如下:
/**
* 冒泡排序
* @param a
*/
public static void bubbleSort(int[] a) {
// 将一个元素依次与其他元素比较,冒泡到最后为一趟
// n个元素只需要将n - 1个数归位,即需要n - 1趟
int count = a.length - 1; // 需要比较的次数
for (int i = 1; i <= count; i++) {
boolean hasSwap = false; // 当前趟有没有发生交换,这样可以优化一下冒泡排序算法。
// 第i趟时,只需比较count-i+1次,因为乘余的数已经排好序了。
for (int j = 0; j <= count - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j + 1];
a[j + 1] = a[j];
a[j] = tmp;
hasSwap = true;
}
}
// 如果没有发生过交换,则说明已经排好序了
if (!hasSwap) {
System.out.println("第" + i + "趟排序已经排好的,结束排序");
break;
}
}
/**
* 冒泡时间复杂度推导:
* 第一趟要迭代 n - 1次
* 第二趟 n - 2次
*
*
* 第n-1趟, 1次
* 累积求和即是 (n - 1) + (n - 2) + (n - 3) + ..... + 1;
* n (n - 1) / 2
* 故时间复杂度是: O(n2)
*/
}
3、快速排序
快速排序是一种基于二分的思想。由于其比较是跳跃式的,故比冒泡排序要快很多,但是最差的情况下等同于冒泡排序。
参考代码如下:
/**
* 快速排序
*
* @param a
* @param left 排序的范围 左起点
* @param right 右起点
*/
public static void quickSort(int[] a, int left, int right) {
// 递归停止条件
if (left > right) {
return;
}
int i = left;
int j = right;
int temp = a[left]; // 选定第一个元素为基准元素
while (i < j) {
// 因为基准元素是最左边的,故首先要从最右边开始找到一个比基准元素小的元素,j为其索引。顺序很重要。同时这里是a[j] >= temp,不能掉了等号。
while (a[j] >= temp && i < j) {
j--;
}
// 从左边开始找到一个比基准元素大的元素,i为其索引
while (a[i] <= temp && i < j) {
i++;
}
// 当i与j没有相遇时才交换,相遇时则表明此次基准数已经归位
if (i < j) {
// 交换i和j的位置
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
// i 与 j 相遇后将基准元素与i处的互换
a[left] = a[i];
a[i] = temp;
// 将基准元素左边的排序
quickSort(a, left, i - 1);
// 同上,将基准元素右边的排序
quickSort(a, j + 1, right);
}
4、插入排序
for (int i = 0; i < nums.length; i++) {
// 当前值与前一个相比, 始终记住这个。
int j = i - 1;
int tmp = nums[i];
while (j >= 0 && tmp < nums[j]) {
// j往后挪动,因为j + 1 = i,当前值已经保存在tmp了,故无需担心nums[j + 1]的值被覆盖。
nums[j + 1] = nums[j];
j--;
}
// 找到相应的位置挺好入
nums[j + 1] = tmp;
}
5、Shell排序
fun shellSort(a: IntArray) {
var size = a.size
var gap = size / 2 // 初始gap为数组长度的一半
while (gap > 0) {
// 如下代码的思想为插入排序思想
for (i in gap until size) {
var tmp = a[i]
var j = i - gap // 如果此时j小于0,则会跳过while循环。a[j+gap]即为a[i]
while (j >= 0 && a[j] > tmp) {
a[j + gap] = a[j]
j -= gap
}
a[j + gap] = tmp
}
gap /= 2 // gap每次减半
}
}
内容总结
以上是互联网集市为您收集整理的常见排序算法全部内容,希望文章能够帮你解决常见排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。