选择排序思想:指针指向数组头,从指针位置到数组尾遍历最小值位置,将该位置与指针位置交换值,指针向后位移一位,循环遍历最小值 实现代码:
/**
* 选择排序
*
* @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换来换去