冒泡排序
7789414-9c7908de122ee2d6.gif
写法:
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for(int i = arr.length - 1; i > 0; i--) {
for(int j = 0; j < i; j++) {
if(arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
代入参数
@Test
public void bubbleSort() {
int[] arr = {1, 2, 3, 4, 55, 6, 67, 8, 88};
int t = 0;
for (int j = arr.length-1; j > 0 ; j--){
for (int i = 0; i < arr.length-1; i++) {
if (arr[i] > arr[i + 1]) {
t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
}
System.out.println(Arrays.toString(arr));
}
//输出结果为:1 2 3 4 6 8 55 67 88
特点: 效率低，容易实现。 思想：每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的为待排序序列，重复上述步 骤直到完成排序
选择排序
selectionSort.gif
@Test
public void selectSort() {
int[] arr = {1, 2, 3, 4, 55, 6, 67, 8, 88};
// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
System.out.println(Arrays.toString(arr));
//输出结果为:1 2 3 4 6 8 55 67 88
}
特点:效率低，容易实现。 思想：每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的为待排序序列，重复上述步 骤直到完成排序
插入排序
insertionSort.gif
@Test
public void insertionSort(){
int[] arr = {1, 2, 3, 4, 55, 6, 67, 8, 88};
int i,j,t=0;
for (i = 1; i < arr.length; i++) {
if (arr[i] < arr[i-1]){
t=arr[i];
for (j=i-1;j>=0 && t < arr[j]; j--){
arr[j+1] = arr[j];
//插入arr[i]
arr[j+1] = t;
}
}
}
System.out.println(Arrays.toString(arr));
//输出结果为:1 2 3 4 6 8 55 67 88
}
特点: 效率低，容易实现。 思想：将数组分为两部分，将后部分元素逐一与前部分元素比较，如果前部分元素比 array[i]小，就将前部 分元素往后移动。当没有比 array[i]小的元素，即是合理位置，在此位置插入 array[i]
quickSort.gif
快速排序
public class QuickSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return quickSort(arr, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
// 设定基准值（pivot）
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
特点: 高效，时间复杂度为 nlogn。 采用分治法的思想：首先设置一个轴值 pivot，然后以这个轴值为划分基准将待排序序列分成比 pivot 大和比 pivot 小的两部分，接下来对划分完的子序列进行快排直到子序列为一个元素为止。
内容整理自菜鸟教程
--https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
