排序算法总结（java实现）
排序算法
介绍：排序分为内部排序和外部排序，内部排序指在内存中进行的排序过程；外部排序指在外存中进行排序的过程，但是此过程建立在多次访问内存的基础上（分成一段段利用内部排序进行排序）。
以下排序均属于内部排序：
一、插入排序
1、直接插入排序
思想：每一步将一个待排序元素，插入到前面已经排好序的序列中去进行比较排序，直到所有元素插完
图解：
代码实现：
/**
* 插入排序
*
* @param arr
*/
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
//当前元素开始与前面排好序元素进行比较
while (j > 0 && arr[j] < arr[j - 1]) {
swap(arr,j,j-1);
j--;
}
}
}
2、希尔排序
思想：把排序序列按照设定的增量进行分组，然后对每一组使用直接插入排序
说明：
- 增量的设定：这个值通常自定义，但是比较常用的增量是gap=length/2（并不是最优）
- 增量的修改：每次经过一次排序后，增量通常需要gap=gap/2，直到增量为1时，停止修改
- 增量的使用：若增量为n，则当前序列需要分为n组，即一组有length/n个元素
- 分组：距离保持一致
图解：
代码实现：
private static int[] sort(int nums[]){
int length = nums.length;
int gap = length/2;//初始化增量
while(gap>=1){
for (int i=0;i<gap;i++){
//得到了本组所有元素，以下对本组元素进行直接插入排序
for (int j=i+gap;j<nums.length;j=j+gap){//默认第一个元素在已排序序列中，故从第二个元素开始插入比较
while(j>i && nums[j-gap]>nums[j]){
int temp = nums[j-gap];
nums[j-gap] = nums[j];
nums[j] = temp;
j=j-gap;
}
}
}
gap = gap/2;
}
return nums;
}
二、选择排序
1、直接选择排序
思想：每次遍历比较出最小值，再拿最小值与当前未排序列的第一个位置元素互换位置。n表示元素个数，则第m次比较（n-m）次
图解：
代码实现：
private static int[] selectSort(int arr[]){
int flag = 0;//记录待比较序列中最小值位置
for(int i=0;i<arr.length-1;i++){
//第i+1轮比较排序
flag = i;
for(int j=i+1;j<arr.length;j++){
if(arr[flag]>arr[j]){
flag=j; //保存最小值位置
}
}
if(flag!=i) {
//判断最小值是否在目标位置，不是则需要进行交换
int temp = arr[flag];
arr[flag] = arr[i];
arr[i] = temp;
}
}
return arr;
}
2、堆排序
思想：
图解：
代码实现：
三、交换排序
1、冒泡排序
思想：进行n-1轮排序（n为元素个数）每轮排序中按照“小在前，大在后”的比较规则进行位置调整，每一轮都会冒出一个最大值在尾部（当前比较序列尾部）
图解：
依次进行n-1轮排序
代码实现：
private int[] bubbleSort(int arr[]){
for(int i=0;i<arr.length-1;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;
}
2、快速排序
思想：在冒泡排序的基础上进行了优化，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两
部分数据分别进行快速排序，整个排序过程可 以 递归进行，以此达到整个数据变成有序序列。
过程说明：
①选取适当的基准数，通常我们选取第一个数为基准数，每一趟依次选取一个基准数，直到结束。
②与基准数比较中，小的换到前面，大的换到后面
③每趟都是先从右边开始比较，发生一次比较赋值（比较位置元素不变，游标不动；把它的值再复制到目标位置，目标位置移动一个单位）后则从另一方向开始
④快速排序停止条件：
图解：
图片来源于 https://www.cnblogs.com/skywang12345/p/3596746.html
代码实现：
/**
* 一次快速排序
* @param array 数组
* @param lo 数组的前下标
* @param hi 数组的后下标
* @return key的下标index，也就是分片的间隔点
*/
public static int partition(int []array,int lo,int hi){
/** 固定的切分方式 */
int key=array[lo];//选取了基准点
while(lo<hi){
//从后半部分向前扫描
while(array[hi]>=key&&hi>lo){
hi--;
}
array[lo]=array[hi];
//从前半部分向后扫描
while(array[lo]<=key&&hi>lo){
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;//最后把基准存入
return hi;
} /**
* 快速排序
* @param array
* @param lo
* @param hi
*/
public static void quickSort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
//进行第一轮排序获取分割点
int index=partition(array,lo,hi);
//排序前半部分
quickSort(array, lo, index - 1);
//排序后半部分
quickSort(array,index+1,hi);
}
四、归并排序
思想：归并排序采用“分治法”思想，将待排序列拆分位子序列，将个子序列内部排序，再合并各子序列，在子序列之间进行排序。
图解：
在治（合并阶段）图解如下：
拿上图中最后一步来举例说明吧
代码实现：
五、基数排序
思想：
图解：
代码实现：
性能比较
最新文章
- Apple Reject
- js通过继承实现私有函数
- Crystal Report 遇到需要登录的问题
- 经典.net试题
- Hadoop入门进阶课程7--Pig介绍、安装与应用案例
- 【BZOJ】【1597】【USACO 2008 Mar】土地购买
- iOS-xib(自定义UITableViewCell)
- Android中ProgressDialog的简单示例
- BZOJ1997 [Hnoi2010]Planar (2-sat)
- #include <bitset>
- OpenFlow硬件交换机制作及刷机教程
- line-height && vertical-align 学习总结
- webp 图形文件操作工具包 win32 (编译 libwebp-20171228-664c21dd 版本)
- js之观察者模式
- JavaScript知识点整理
- python删除文件与目录的方法
- 用Maven构建单机Mahout项目
- mysql的转储SQL文件
- python并发编程之多进程理论知识
- java代码----substring()方法是按索引截取字符串。。。下标0开始