一、排序介绍
排序，是将一组数据按照指定顺序排列的过程。
1.1 分类
内部排序
将需要处理的所有数据都加载到内存中进行排序。
外部排序
数据量过大，无法全部加载进内存，需要借助外部存储进行排序。
二、冒泡排序
package a06.sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {2, 6, 9, 3, 8, 1, -4};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
//冒泡排序，相邻两个元素依次进行对比，将大的元素交换到后面
//标志是否已经有序
boolean flag;
//一共进行数组大小-1次大循环
for (int i = 0; i < arr.length - 1; i++) {
flag = true;
for (int j = 0; j < arr.length - i - 1; j++) {
//相邻两个元素进行比较
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if(flag){
break;
}
}
}
}
三、选择排序
package a06.sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = {2, 6, 9, 3, 8, 1, -4};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//选择排序，每次从未排序列中选择一个最小的放入已排序列。
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
四、插入排序
4.1 普通插入排序
4.2 希尔排序
package example.test;
import java.util.Arrays;
/**
* @author Tao
* @Date 2020/10/16
* @Time 14:51
*/
public class InsertSort {
public static void main(String[] args) {
// j i
int[] arr = {-1, 0, 8, 1, 4, 9, 2, 3, 7};
System.out.println(Arrays.toString(arr) + "\n");
sort(arr);
System.out.println("\n" + Arrays.toString(arr));
System.out.println("\n----------\n希尔排序\n----------");
int[] arr2 = {-1, 0, 8, 1, 4, 9, 2, 3, 7};
System.out.println(Arrays.toString(arr2));
shell(arr2);
System.out.println("\n" + Arrays.toString(arr2));
}
private static void shell(int[] arr) {
// j i
// {-1, 0, 8, 1, 4, 9, 2, 3, 7}
// 希尔排序，插入排序的改进版本，将待排序的列按间隙分组，每组调用插入排序，则小元素被取到前边。
for (int group = arr.length / 2; group > 0; group /= 2) {
System.out.println("group="+group);
// i:未排序
for (int i = group; i < arr.length; i++) {
int j=i;
if(arr[j]<arr[j-group]){
int temp = arr[i];
while(j-group>=0 && temp<arr[j-group]){
arr[j] = arr[j-group];
j-=group;
System.out.println(Arrays.toString(arr));
}
arr[j]=temp;
System.out.println(Arrays.toString(arr));
}
}
}
}
private static void sort(int[] arr) {
// i
// {-4, -1, 3, 4, 1, 8, 9, 2, 7}
// 插入排序，每次从未选择的取出一个，插入到已排序列
// i:未排序开始索引
for (int i = 1; i < arr.length; i++) {
int j=i;
if(arr[j]<arr[j-1]){
int temp = arr[i];
while(j-1>=0 && temp<arr[j-1]){
arr[j] = arr[j-1];
j--;
System.out.println(Arrays.toString(arr));
}
arr[j]=temp;
System.out.println(Arrays.toString(arr));
}
}
}
}
五、快速排序
package a06.sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {2, 6, 9, 3, 8, 1, -4};
sort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int start, int end) {
//快速排序，挖坑填数+分治法
if (start >= end) {
return;
}
int i = start;
int j = end;
int flag = arr[start];
// 从右向左找第一个小于x的数
while (i < j && arr[j] >= flag) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
// 从左向右找第一个大于等于x的数
while (i < j && arr[i] <= flag) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
arr[i] = flag;
sort(arr,start,i-1);
sort(arr,i+1,end);
}
}
六、归并排序
package a06.sort;
import java.util.Arrays;
public class MergeSort {
//归并排序，分治法——先分后治
public static void main(String[] args) {
int[] arr = {2, 6, 9, 3, 8, 1, -4};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int middle = (start + end) / 2;
sort(arr, start, middle);
sort(arr, middle + 1, end);
merge(arr, start, middle, middle + 1, end);
}
private static void merge(int[] arr, int lStart, int lEnd, int rStart, int rEnd) {
int[] result = new int[rEnd - lStart + 1];
int index = 0;
int left = lStart;
while (lStart <= lEnd && rStart <= rEnd) {
if (arr[lStart] <= arr[rStart]) {
result[index++] = arr[lStart++];
} else {
result[index++] = arr[rStart++];
}
}
while (lStart <= lEnd) {
result[index++] = arr[lStart++];
}
while (rStart <= rEnd) {
result[index++] = arr[rStart++];
}
index = 0;
for (int i = left; i <= rEnd; i++) {
arr[i] = result[index++];
}
}
}
七、归并排序
package a06.sort;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr = {2, 6, 9, 3, 8, 1, 4};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//基数排序，将整数按位数切割成不同的数字
//得到最大值位数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxSize = (max + "").length();
//由整数0-9组成的桶，每个桶都是一个数组
int[][] bucket = new int[10][arr.length];
//统计桶中元素的个数
int[] count = new int[10];
//位数表示的值，从个位数开始
//入桶
for (int i = 0, temp = 1; i < maxSize; i++, temp *= 10) {
for (int j = 0; j < arr.length; j++) {
int element = arr[j] / temp % 10;
bucket[element][count[element]] = arr[j];
count[element]++;
}
//出桶
int index = 0;
for (int k = 0; k < count.length; k++) {
if (count[k] != 0) {
for (int l = 0; l < count[k]; l++) {
arr[index++] = bucket[k][l];
}
}
count[k] = 0;
}
System.out.println(Arrays.toString(arr));
}
}
}
七、对比
k：桶的个数
Q.E.D.
Comments | 0 条评论