几种排序算法总结：
选择排序-简单选择排序
基本思想：在要排序的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推，直到第n-1个元素和第n个元素比较为止。
简单选择排序的改进——二元选择排序
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
java实现
public class SelectSort {
public static void main(String[] args) {
// int[] array = {3, 9, -1, 10, 20};
// sort(array);
// System.out.println(Arrays.toString(array));
int[] array = new int[80000];
for (int i = 0; i < 80000; i++) {
array[i] = (int) (Math.random() * 80000);
}
Instant inst1 = Instant.now();
sort(array);
Instant inst2 = Instant.now();
System.out.println("时间" + Duration.between(inst1, inst2).getSeconds());
}
static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int temp = array[i];
int tempMinIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[tempMinIndex] > array[j]) {
tempMinIndex = j;
temp = array[j];
}
if (tempMinIndex != i) {
// temp = array[tempMinIndex];
array[tempMinIndex] = array[i];
array[i] = temp;
}
}
// System.out.println("第" + i + "次排序，结果为" + Arrays.toString(array));
}
}
}
js实现：
function selectionSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var index = i; //index做指针，指向当前i位置之后（包括i）的最小的数的下标
var temp;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
return arr;
}
交换排序-冒泡排序
实现思路：相邻两两比较交换
java实现
public class BubbleSort {
public static void main(String[] args) {
// int[] array = {3, 9, -1, 10, 20};
// sort(array);
// System.out.println(Arrays.toString(array));
}
static void sort(int[] array) {
int temp;
boolean flag = false;
for (int i = 0; i < array.length -1; i++) {
// 0至array.length -1 -i是还未处理完的的，剩下的是筛选出来的
for (int j = 0; j < array.length -1 -i; j++) {
if(array[j] > array[j + 1]) {
flag = true;
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
// 因为比较的传递性，前一个都比后一个小的话，就不用再继续比较了
if(!flag) {
break;
} else {
flag = false;
}
System.out.println("第" + i + "次排序，结果为" + Arrays.toString(array));
}
}
}
js实现：
function bubbleSort (arr) {
for (var i = 0; i < arr.length-1; i++) {
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
交换排序-快速排序（直接看菜鸟教程，是先序遍历的递归，找到基准值的下标，然后以下标为界，左右递归）
思路：递归进行分组；以left下标所对应的值为base值，然后从右往左找，找到比base小的就把值赋给left（left已经被存在base里了），此时换方向，从左往右找，找到比base大的值就赋值给right（right已经赋值给left了）；最后left==right了，再把base值赋值给left和right重合的地方
java实现
public static void main(String[] args) {
// int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
// sort(arr, 0, arr.length - 1);
// System.out.println(Arrays.toString(arr));
int[] array = new int[80000];
for (int i = 0; i < 80000; i++) {
array[i] = (int) (Math.random() * 80000);
}
LocalDateTime localDateTime1 = LocalDateTime.now();
System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
sort(array, 0, array.length - 1);
LocalDateTime localDateTime2 = LocalDateTime.now();
System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
}
static void sort(int[] arr, int left, int right) {
if (left < right) {
int base = arr[left];
int l = left;
int r = right;
while (l < r) {
while (arr[r] >= base && l < r) {
r--;
}
arr[l] = arr[r];
while (arr[l] < base && l < r) {
l++;
}
arr[r] = arr[l];
}
arr[l] = base;
sort(arr, left, l-1);
sort(arr, l + 1, right);
}
}
}
javascript实现：
function division (arr, left, right) {
var base = arr[left];
while (left < right) {
while (arr[right] >= base && left < right) {
right--;
}
arr[left] = arr[right];
while (arr[left] <= base && left < right) {
left++;
}
arr[right] = arr[left];
}
arr[left] = base;
return left;
}
function quickSort (arr, left, right) {
if (left < right) {
var baseIndex = division(arr, left, right);
quickSort(arr, left, baseIndex - 1);
quickSort(arr, baseIndex + 1, right);
}
return arr;
}
归并排序，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
思路：后序遍历思想（递归），拆分至最底层，然后合并。有序链表的合并。temp作为临时数组，把排序的数据放到temp中（temp数组是必须的），然后copy给原数组
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(temp));
}
static void mergeSort(int[] arr, int left, int right, int[] temp) {
int mid = (left + right)/2;
if(left < right) {
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
// 两个有序链表的合并
merge(arr, left, mid, right, temp);
}
}
static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int leftIndex = left;
int tempIndex = left;
int rightIndex = mid + 1;
while (leftIndex < mid + 1 && rightIndex < right+1) {
if (arr[leftIndex] < arr[rightIndex]) {
temp[tempIndex] = arr[leftIndex];
leftIndex++;
} else {
temp[tempIndex] = arr[rightIndex];
rightIndex++;
}
tempIndex++;
}
if(leftIndex == mid + 1 && rightIndex < right+1) {
for(int i = rightIndex; i < right +1; i++) {
temp[tempIndex] = arr[i];
tempIndex++;
}
}
if(leftIndex < mid +1 && rightIndex == right + 1) {
for(int i = leftIndex; i < mid +1; i++) {
temp[tempIndex] = arr[i];
tempIndex++;
}
}
// 将temp copy给原数组
int tempLeft = left;
while (tempLeft < right +1) {
arr[tempLeft] = temp[tempLeft];
tempLeft++;
}
}
基数排序（桶排序）
不太好描述，就不写了
public class RadixSort {
public static void main(String[] args) {
// int[] arr = {53, 3, 542, 748, 14, 214};
// sort(arr);
// System.out.println(Arrays.toString(arr));
int[] array = new int[80000];
for (int i = 0; i < 80000; i++) {
array[i] = (int) (Math.random() * 80000);
}
LocalDateTime localDateTime1 = LocalDateTime.now();
System.out.println("执行前" + localDateTime1.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
sort(array);
LocalDateTime localDateTime2 = LocalDateTime.now();
System.out.println("执行后" + localDateTime2.format(DateTimeFormatter.ofPattern("yyyy-MM-DD "
+ "HH-mm-ss-SSS")));
}
static void sort(int[] arr) {
// 定义一个二维数组，表示10个桶
int[][] bucket = new int[10][arr.length];
// 记录每个桶的下标
int[] bucketElements = new int[10];
// 记录最大数，为了获得最大的位数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
for (int l = 1; l < max; l=l*10) {
// 记录位数
int digit = 0;
for (int j = 0; j < arr.length; j++) {
digit = arr[j]/l% 10;
bucket[digit][bucketElements[digit]] = arr[j];
bucketElements[digit] += 1;
}
int tempIndex = 0;
for (int i = 0; i < bucketElements.length; i++) {
if (bucketElements[i] != 0) {
for (int j = 0; j < bucketElements[i]; j++) {
arr[tempIndex] = bucket[i][j];
tempIndex++;
}
bucketElements[i] = 0;
}
}
}
}
}
网友评论