1.插入排序：
插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。
java实现代码：
public class insertion {
public static int[] sort(int[] arr){
if(arr.length==1)
return arr;
if(arr.length==0)
return null;
else{
int N=arr.length;
for (int i=1;i<N;i++)
{
for(int j=i;j>0;j--)
{if(arr[j]<arr[j-1])
{int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;}
else{
break;
}
}
}
}
return arr;
}
}
冒泡排序：
冒泡排序思想
基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
直观表达，每一趟遍历，将一个最大的数移到序列末尾。
算法描述
比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位
因此需要n-1趟；
引自https://www.jianshu.com/p/1458abf81adf
java代码实现：
public class Bubble {
public static int[] sort(int[] arr){
if(arr.length==1)
return arr;
if(arr.length==0)
return null;
else{
for(int i=0;i<arr.length;i++)
for(int j=0;j<arr.length-1-i;j++)
{
if(arr[j]>arr[j+1])
{int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;}
}
}
return arr;
}
}
3.选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
步骤：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
java实现：
public class Selection {
public static int[] sort(int[] arr){
if(arr.length==1)
return arr;
if(arr.length==0)
return null;
else {
for (int i = 0; i < arr.length; i++) {
int min = arr[i];//将i后的最小值取出
int minIndex=i;//得到最小值的下标值
for (int j = i; j < arr.length; j++) {
if(arr[j]<min)
{min=arr[j];
minIndex=j;
}
}
//交换最小值和i的位置
int temp=arr[i];
arr[i]=min;
arr[minIndex]=temp;
}
}
return arr;
}
}
4.堆排序
堆排序是通过堆实现的，堆通常是一个可以被看做一棵完全二叉树的数组对象。这里就不赘述了，主要是代码实现
public class Heapsort {
static int[] heapSort(int []a,int len){
//注意这里的下标值是从0开始的
int i;
for(i=len/2-1;i>=0;i--){ /*从第一个非叶节点开始把a[]构造成一个大顶堆*/
HeapAdjust(a,i,len);
}
for(i=len-1;i>0;i--){
swap(a,0,i); /*交换堆顶最大元素和堆尾最小元素*/
HeapAdjust(a,0,i-1); /*把交换后的堆a[0,i-1]，再次构造成大顶顶，使堆顶元素为最大值*/
}
return a;
}
static void HeapAdjust(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
static void swap(int a[],int low,int high){
int temp=a[low];
a[low]=a[high];
a[high]=temp;
}
}
这里可以看出，堆排序的效率远高于其他。
5.java自带的Array.sort()
在java中，设置一个阈值为7,如果待排序数组的长度小于7,则使用插入排序，如果待排序数组的长度大于等于7,则使用归并排序。
6.快速排序
通过一趟排序将要排序的数据bai分割成独立du的两部分，其中一部分的所有数据都zhi比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
java实现如下：
public class kuaiPai {
public static void Quick_Sort(int[] arr, int begin, int end){
if(begin>end)
return;
int temp=arr[begin];//temp为基准位
int i=begin;
int j=end;
while(i<j)
{ while(arr[j]>=temp&&i<j)//右边的总比基准大
j--;
while(arr[i]<=temp&&i<j)//左边的总比基准小
i++;
if(j>i)
{
int x=arr[i];
arr[i]=arr[j];
arr[j]=x;
}
}
arr[begin]=arr[i];
arr[i]=temp;
Quick_Sort(arr,begin,i-1);
Quick_Sort(arr,i+1,end);
}
}
可以看出，在100000规模的数字的时候，快排用了44毫秒
从上面的对比，我们可以知道当数组规模为100000时，排序的时间：冒泡>选择>插入>快速>堆排序>java里自带的。
京公网安备 11010502036488号