排序就是将输入的数字按照从小到大的顺序进行排列。由于排序是一个比较基础的问题,所以排序算法的种类也比较多。最近学习了几种常见的排序算法,下面介绍如何使用java代码实现对数组进行从下到大排序。
一、冒泡排序
1、概念
冒泡排序通过序列左边开始比较相邻位置数字的大小,左边数字大于右边了交换位置,只到最大的到最右边,然后再从左边开始比较相邻位置的数字,左边大于右边交换位置,只到最大的到右边第二个位置,循环操作,在这个过程中,数字会像泡泡一样,慢慢从左往右“浮”到序列的右端,所以这个算法才被称为“冒泡排序”。看图解理解此概念很容易。
2、图解
3、代码实现
public class BubbleSortTest {
public static void main(String[] args) {
int[] arr = new int[]{11, 2, 3, 5, 7, 4, 10, 8, 9};
BubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void BubbleSort(int[] arr) {
//从右边开始循环遍历数组
for (int i = arr.length - 1; i > 0; i--) {
//遍历未排序的数组
for (int j = 0; j < i; j++) {
//相邻位置左边值大于右边,交换位置,将最大值最后换到待排序列最右边
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
二、选择排序
1、概念
选择排序就是从左边第一个开始,遍历右边序列找到最小的值与左边第一个数据交换位置,这样左边第一个数字就是整个序列最小的,然后从左边第二个开始,遍历右边的序列找到最小的值与左边第二个交换位置,依次类推,只到右边待排序的数据个数为0,结束循环,此时数组排序成功,因为每次循环后,左边的序列都是有序的。看图解理解此概念很容易。
2、图解
3、代码实现
public class SelectQueueTest {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 7, 3, 7, 5, 7, 4, 9, 0, 8, 6, 3, 3, 4, 3, 4};
SelectQueue(arr);
System.out.println(Arrays.toString(arr));
}
private static void SelectQueue(int[] arr) {
//总左边第一个开始,循环遍历每一个值
for (int i = 0; i < arr.length; i++) {
//默认序列中最小值的位置是待排序列第一个
int min = i;
//找到比默认最小值更小的,更新默认最小值位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
//默认最小值位置如果更新了,说明最小值在右边序列中,交换数值
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
}
三、插入排序
1、概念
插入排序默认左边是有序的,将待排序列第一个插入到左边对应的位置,保证每次插入左边序列都是有序的,插入数据时从右向左遍历左边有序数组,大于待插入数据,交换位置,只到小于待插入的数据停止比较,此时左边有序数组多了一位,将待插入值放进去左边序列依然有序,依次类推,插入剩余的数字。看图解理解此概念很容易。
2、图解
3、代码实现
public class InsertQueueTest {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 7, 3, 7, 5, 7, 4, 9, 0, 8, 6, 3, 3, 4, 3, 4};
InsertQueue(arr);
System.out.println(Arrays.toString(arr));
}
public static void InsertQueue(int[] arr) {
//循环遍历数组
for (int i = 1; i < arr.length; i++) {
//从右往左遍历左边已排序序列
for (int j = i; j > 0; j--) {
//如果待插入值大于遍历的左边待排序值,结束遍历左边序列
if (arr[j] > arr[j - 1]) {
break;
} else {
//如果待插入值小于遍历的左边待排序值,交换位置,接着循环,
// 只到将待插入值放进去左边序列有序
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
}
四、快速排序
1、概念 快速排序要比上面几个排序难度大些了,排序的效率也更高,实现方式就是在数组中找一个基准数,将大于基准数的值放到基准数右边,小于的放到左边,然后将小于基准数的左边序列再次选择一个基准数,大于基准数的右边序列也再次选择一个基准数,循环执行上述操作,只到子序列都剩一个数字时,停止循环,此时排序成功。可以看下面图解理解此概念,比较难,多看几遍就理解了。
补充:快速排序是一种“分治法”。它将原本的问题分成两个子问题(比基准值小的数和比基准值大的数),然后再分别解决这两个问题。子问题,也就是子序列完成排序后,再像一开始说明的那样,把他们合并成一个序列,那么对原始序列的排序也就完成了。不过,解决子问题的时候会再次使用快速排序,甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候,排序才算完成。
2、图解
3、代码实现
public class QuickQueueTest {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 7, 3, 7, 5, 7, 4, 9, 0, 8, 6};
QuickQueue(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* @param arr 待排数组
* @param start 开始位置下标
* @param end 结束位置下标
*/
private static void QuickQueue(int[] arr, int start, int end) {
//开始位置下标不小于结束位置下标时,说明子序列不可再分,停止执行快排
if (start < end) {
//将开始位置的数字作为基准数
int target = arr[start];
int left = start;
int right = end;
//左边小于右边时,基准数赋值给下标为left的位置
while (left < right) {
//从右往左循环遍历数组,找到第一个小于基准数的位置
while (arr[right] >= target && left < right) {
right--;
}
//将右边第一个小于基准数的值赋值到左边,
arr[left] = arr[right];
//从左边开始遍历,找到大于基准数的第一个位置
while (arr[left] <= target && left < right) {
left++;
}
//把该值弄到右边,给right位置
arr[right] = arr[left];
}
//最后将基准树赋值给下标为left的值,
// 此时,从基准数位置看,大于的在右边,小于基准数的在左边
arr[left] = target;
//将基准数左边的进行快排
QuickQueue(arr, start, left);
//将基准数右边的进行快排
QuickQueue(arr, left + 1, end);
}
}
}
五、总结 以上就是对这几个排序的java实现