排序算法有很多，这里简单谈谈冒泡，插入，选择排序算法：
1、冒泡排序：这个应该是比较常见，而且面试经常会考的。该排序思路是 相邻两个比较，不符合目标排序的则调换两个元素位置，经过一轮比较，可以将最大或最小值放到头部或尾部。 以此类推，第二轮对剩下的n-1个元素进行该操作。n轮之后排序完成。
2、插入排序：插入排序是将目标序列分成两部分，已排序部分和未排序部分。以升序来举例子：做右边未排序部分取第一个元素，从右到左一次跟已排序元素进行比较，遇到更大的就将被比较元素后移一位，直到遇到较小元素，将该元素放在被比较元素后面。
3、选择排序：也是将元素分为已排序部分和未排序部分。循环未排序部分，找到最小元素，并将该元素与第一个元素交换位置。一次类推，将剩下的未排序部分按照这个规律经行处理即可。
java 数组实现代码如下：（仅供参考，欢迎大家指出其中可以优化的地方）
package com.jdwa;
import java.util.Arrays;
public class TestSort {
public static void main(String[] args) {
int n = 10000;
int[] bubble = new int[n];
int[] insert = new int[n];
int[] select = new int[n];
for (int k = 0 ; k< n;k++){
int l = (int)(n*Math.random()); //随机生成0-100的数
bubble[k] = l;
insert[k] = l;
select[k] = l;
}
bubbleSort(bubble);
System.out.println(Arrays.toString(bubble));
System.out.println("==================");
insertSort(insert);
System.out.println(Arrays.toString(insert));
System.out.println("+++++++++++++++++++++");
selectSort(select);
System.out.println(Arrays.toString(select));
}
/**
* 冒泡排序:
* 思路：第一轮将最大或最小元素通过比较与交换，送到头部或尾部，剩余元素以此类推，一次从到正或倒数第二，三，四。。。等位置
* @param arr
* @return
*/
public static void bubbleSort(int[] arr){
Long beg = System.currentTimeMillis();
int n = arr.length;
if ( n <= 1 ) {
return;
}
for ( int i = 0 ;i < n ; i ++) {
// 用于标记本次循环有没有数据交换，如有没有说明已排序完成，直接退出
boolean flg = false;
//n-i个元素，没两个元素进行比较，故需要 n - i -1比较
for ( int j = 0 ; j < n - i -1 ; j++ ) {
if (arr[j] > arr[j+1]) {
flg = true;
//升序排列，如果前面的数据大则交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if (!flg) {
break;
}
}
System.out.println(System.currentTimeMillis() - beg);
}
/**
* 升序排列
* 选择第i个元素value，跟前面的元素做对比，升序则需要从后往前，所以内循环的下标依次递减
*
* 思路：将数组分为两部分左边是已排序部分 右边是未排序部分
* 以第二个元素为例， 先将arr[1]（未排序最左边元素）取出暂存，并将其值依次从右向左跟已排序部分比较，遇到更大的则将元素后移一位（因为未排序最左边位置元素已暂存，不用担心覆盖）
* 直到遇到更小的元素，跳出循环。将暂存的第二个元素 存到 跳出循环时 比较的元素arr[j]的右边位置，即arr[j+1]
* @param arr
*/
public static void insertSort(int[] arr){
Long beg = System.currentTimeMillis();
int n = arr.length;
if ( n <= 1 ) {
return;
}
for (int i = 0 ; i < n ; i ++){
int value = arr[i];
int j = i-1;
for ( ; j >= 0 ; j--) {
if (arr[j] > value){
arr[j+1] = arr[j]; //依次移动数据
} else {
break;
}
}
arr[j+1] = value;
}
System.out.println(System.currentTimeMillis() - beg);
}
public static void selectSort(int[] arr) {
Long beg = System.currentTimeMillis();
int n = arr.length;
if ( n <= 1 ) {
return;
}
for (int i = 0 ; i < n ; i ++){
int value = arr[i];
int j = i+1;
//循环，最小值在最后一个元素
for ( ; j < n-1 ; j++) {
if (arr[j] < arr[j+1]) {
//升序排列，如果前面的数据大则交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
//arr[i]与arr[n-1]交换
int tmp = arr[i];
arr[i] = arr[n-1];
arr[n-1] = tmp;
}
System.out.println(System.currentTimeMillis() - beg);
}
}
某次运行结构如下：
143
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]
==================
33
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]
+++++++++++++++++++++
153
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]
Process finished with exit code 0
网友评论