选择排序和快速排序(Java)
2023-04-18 12:32:15 时间
选择排序思想:指针指向数组头,从指针位置到数组尾遍历最小值位置,将该位置与指针位置交换值,指针向后位移一位,循环遍历最小值 实现代码:
/**
* 选择排序
*
* @param nums
*/
public void selectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
//从i指针开始遍历,查找最小的一个
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = nums[minIndex];
nums[minIndex] = nums[i];
nums[i] = temp;
}
}
}
快速排序思想:基于选择排序,但有很大不一样。 1.从数组中取出第一个元素
2.一个high指针指向数组尾,一个指针low指向数组头
3.先从high开始查找,获取“比取出的元素“的值(31)小的索引,放入low指针位置
4.再从low位置开始查找,获取“比取出的元素“的值(31)大的索引,放入high指针位置
5.循环第3步,直到两个指针重合
6.将”取出的元素“的值(31)放入指针位置
7.从该位置进行二分,以数组头部到low-1位置和low+1到数组尾部重复第1步操作
实现代码:
/**
* 快速排序
*
* @param nums
* @param start
* @param end
*/
public void quickSort(int[] nums, int start, int end) {
if (end <= start) {
return;
}
//取出的元素
int take = nums[start];
int low = start;
int high = end;
boolean isReverse = true;//默认从尾部开始找
next:
while (low < high) {
if (isReverse) {//从high找比 take 小的值
while (low < high) {
if (nums[high] <= take) {
nums[low++] = nums[high];
isReverse = false;
continue next;
}
high--;
}
} else {
while (low < high) {//从low开始找比 take 大的值
if (nums[low] >= take) {
nums[high--] = nums[low];
isReverse = true;
continue next;
}
low++;
}
}
}
//将take赋值
nums[low] = take;
//二分再排序
quickSort(nums, start, low - 1);
quickSort(nums, low + 1, end);
}
测试代码:
int[] nums = new int[]{5, 7, 1, 3, 9, 0, 1};
quickSort(nums, 0, nums.length - 1);
for (int i : nums) {
System.out.print(i + " ");
}
结果: 0 1 1 3 5 7 9
快速排序对大数据量排序有很高的性能,但是只适用于顺序表,由于链表不能直接访问,交换起来效率很低。另外大量重复数据也会对快速排序性能有影响,重复的部分会在high和low换来换去
相关文章
- 解读 Java 云原生实践中的内存问题
- Socket是并发安全的吗
- GitHub Copilot最新升级!61%的Java开发者用来摸鱼,工作效率提升55%
- 承载高并发的缓存技术究竟是什么?
- 云原生Java框架-Micronaut
- 七个用于云原生世界的Java框架
- JAVA回调机制(CallBack)详解
- 面试感悟----一名3年工作经验的程序员应该具备的技能
- Java 征途:行者的地图
- java中文乱码解决之道(一)-----认识字符集
- 关于如何提高Web服务端并发效率的异步编程技术
- 为什么做java的web开发我们会使用struts2,springMVC和spring这样的框架?
- 如何在高并发环境下设计出无锁的数据库操作(Java版本)
- 高并发服务端分布式系统设计概要(上)
- C#综合揭秘——Entity Framework 并发处理详解
- 做Java开发这一年
- java/.net语言及IDE简易对比
- 编程十年 (8):歪打正着C#
- 分清“语言/规范”以及“平台/实现”,以及跨平台.NET开发
- C#之int挑战Java之Integer