前言
现在排序算法经过长时间的演变，发展处各种不同的排序算法。不得不说在日常开发以及日后的研究生活中还是比较常见以及使用的。再此对各种排序算法做一个记录，方便日后比较和查阅。
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
直接插入排序(插入排序)
- 介绍
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复步骤2
- 最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n2)的复杂度。
- 最差复杂度：当输入数组为倒序时，复杂度为O(n2)
比较适合用于“少量元素的数组”。
代码
import java.util.*;
class Untitled {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
directInsertSort(sort);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
希尔排序
冒泡排序
import java.util.*;
class test1 {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
buddleSort(sort);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
public static void buddleSort(int[] sort){
for (int i = 1;i < sort.length;i++) {
for (int j = 0;j < sort.length - i;j++) {
if (sort[j] > sort[j+1]) {
int temp = sort[j];
sort[j] = sort[j + 1];
sort[j + 1] = temp;
}
}
}
}
}
- 排序效果
选择排序
import java.util.*;
class Untitled {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
selectSort(sort);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
public static void selectSort(int[] sort){
for (int i = 0; i < sort.length - 1;i++) {
for (int j = i + 1;j < sort.length;j++) {
if (sort[j] < sort[i]) {
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
示例
排序效果
快速排序
import java.util.*;
class Untitled {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
public static void quickSort(int[] sort, int start, int end) {
// 设置关键数据key为要排序数组的第一个元素，
// 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
int key = sort[start];
// 设置数组左边的索引，往右移动判断比key大的数
int i = start;
// 设置数组右边的索引，往左移动判断比key小的数
int j = end;
// 如果左边索引比右边索引小，则还有数据没有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换
// 即保持了key左边的数比key小，key右边的数比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//递归调用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
归并排序
- 排序效果
堆排序
