八种排序算法
一 冒泡排序
步骤
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
举个栗子
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
-
第一趟排序(外循环)
-
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 | -
第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 | -
第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 | -
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 | -
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
-
- 第二趟排序(外循环)
-
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 | -
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | -
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 | -
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
-
- 第三趟排序(外循环)
-
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | -
第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | -
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 |5| 6 | 9 |
交换后状态| 1 | 2 | 4 |5| 6 | 9 | -
第四趟排序(外循环)无交换
-
第五趟排序(外循环)无交换
-
排序完毕,输出最终结果1 2 4 5 6 9
冒泡排序代码
public class BubbleSort
{
public void sort(int[] a)
{
int temp = 0;
for (int i = a.length - 1; i > 0; --i)
{
// 遍历数组，找到范围内的最大值
for (int j = 0; j < i; ++j)
{
// 交换两个数，把大的数放在后面
if (a[j + 1] < a[j])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
使用场景：
8个数据以下的排序适合使用，效率最高
二 选择排序
处理步骤：
-
(1)从待排序序列中，找到关键字最小的元素；
-
(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
-
(3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
image.png
选择排序的代码实现
public void selectionSort(int[] list) {
// 需要遍历获得最小值的次数
// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
for (int i = 0; i < list.length - 1; i++) {
int index = i; // 用来保存最小值得索引
// 寻找第i个小的数值
for (int j = i + 1; j < list.length; j++) {
if (list[index] > list[j]) {
index = j;
}
}
// 将找到的第i个小的数值放在第i个位置上
if(index!=i) {//表示打到过最小值
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
分治法
分治法的精髓：
- 分--将问题分解为规模更小的子问题；
- 治--将这些规模更小的子问题逐个击破；
- 合--将已解决的子问题合并，最终得出“母”问题的解；
三 快速排序
下图一张展示一次快排的步骤，另一种展示全部快排的步骤
一次排序交换过程.gif
快排的过程.png
快速排序的代码 （前序遍历）
quickSort(array,0,array.length-1);
//快速排序 31 12 68 40 59 21 x=31
public static void quickSort(int[] array,int begin,int end){
if(end-begin<=0) {return ;}
int x=array[begin];//31
int low=begin;//0
int high=end;//5
//由于会在两头取数据，需要一个方向
boolean direction =true;
//开始进行数据的移动
L1:
while(low<high){
if(direction){//从右往左找
for(int i=high;i>low;i--){
if(array[i]<=x){
array[low++]=array[i];
high=i;
direction=!direction;
continue L1;
}
}
high=low;
}else{
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low=i;
direction=!direction;
continue L1;
}
}
low=high;
}
}
//把最后找到的值放入中间位置
array[low]=x;
//开始完成左右两边的操作
quickSort(array,begin,low-1);//L
quickSort(array,low+1,end);//R
}
应用场景：
- 数据量大并且是线性结构
不适用场景：
- 有大量重复数据的时候，性能不好
- 单向链式结构处理性能不好（一般来说，链式都不使用）
四 归并排序
归并操作的工作原理如下：
-
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
-
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
-
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
-
重复步骤3直到某一指针超出序列尾
-
将另一序列剩下的所有元素直接复制到合并序列尾
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
image.png
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成数组
int[] leftArray=new int[leftSize];
int[] rightArray=new int[rightSize];
//填充左边的数组
for(int i=left;i<mid;i++){
leftArray[i-left]=array[i];
}
//填充右边的数组
for(int i=mid;i<=right;i++){
rightArray[i-mid]=array[i];
}
//合并数组
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k]=leftArray[i];
k++;
i++;
}else{
array[k]=rightArray[j];
k++;
j++;
}
}
while(i<leftSize){//左边还有数据没用完
array[k]=leftArray[i];
k++;
i++;
}
while(j<rightSize){//右边还有数据没用完
array[k]=rightArray[j];
k++;
j++;
}
}
public static void mergeSort(int array[],int left,int right){
if(left==right){
return;
}else{
int mid=(left+right)/2;
mergeSort(array,left,mid);//排好左边 L
mergeSort(array,mid+1,right);//排好右边 R
merge(array,left,mid+1,right);//再对左右进行合并 D
}
}
五 链式基数排序
原理
步骤
radixSort.png
clsaa Mahjong{
public int rank;//点数
public int suit;//花色
}
public static void radixSort(LinkedList<Mahjong> list){
//先对点数进行分组
LinkedList[] rankList=new LinkedList[9];
for (int i=0;i<rankList.length;i++){
rankList[i]=new LinkedList();
}
//把数据一个一个的放入到对应的组中
while(list.size()>0){
//取一个
Mahjong m=list.remove();
//放到组中 rank：点数
rankList[m.rank-1].add(m);
}
//把9个组合到一起
for (int i = 0; i < rankList.length; i++) {
list.addAll(rankList[i]);
}
//先花色数进行分组
LinkedList[] suitList=new LinkedList[3];
for (int i=0;i<suitList.length;i++){
suitList[i]=new LinkedList();
}
//把数据一个一个的放入到对应的组中
while(list.size()>0){
//取一个
Mahjong m=list.remove();
//放到组中
suitList[m.suit-1].add(m);
}
//把3个组合到一起
for (int i = 0; i < suitList.length; i++) {
list.addAll(suitList[i]);
}
}
测试代码
@org.junit.Test
public void testRadixSort(){
LinkedList<Mahjong> list=new LinkedList<Mahjong>();
list.add(new Mahjong(3,1));
list.add(new Mahjong(2,3));
list.add(new Mahjong(3,7));
list.add(new Mahjong(1,1));
list.add(new Mahjong(3,8));
list.add(new Mahjong(2,2));
list.add(new Mahjong(3,2));
list.add(new Mahjong(1,3));
list.add(new Mahjong(3,9));
System.out.println(list);
radixSort(list);
System.out.println(list);
}
六 插入排序
insertSort.png
@org.junit.Test
public void testInsertSort(){
int[] array=new int[]{3,9,1,2,5,4,7,8,6};
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
shellSort(array,3);
shellSort(array,1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
//直接插入排序
public void insertSort(int[] array){
for(int i=1;i<array.length;i++){
int j=i;
int target=array[i];//表示想插入的数据
while(j>0 && target<array[j-1]){//如果插入的数据小于数组的前一个时
array[j]=array[j-1];
j--;
}
array[j]=target;
}
}
七 希尔排序
shellSort.png
//希尔排序 step表示的是步长
public static void shellSort(int[] array,int step){
//3 9 1 2 5 4 7 8 6
//2 5 1 3 8 4 7 9 6
for(int k=0;k<step;k++) {//对步长的定位，选择每次操作的开始位置
for(int i=k+step;i<array.length;i=i+step){//i表示从第2个数开始插入
int j=i;
int target=array[i];//表示想插入的数据
while(j>step-1 && target<array[j-step]){//如果插入的数据小于数组的前一个时
array[j]=array[j-step];
j=j-step;
}
array[j]=target;
}
}
}
八 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
//堆排序
public static void heapSort(int[] array){
//开始建堆
//从最后一个非叶子(array.length-1)/2结点开始建
for (int i = (array.length-1)/2; i>=0; i--) {
createHeap(array,array.length,i);
}
//开始边输出堆顶，边调整堆
int n=array.length;//表求堆中元素的个数
while(n>0){
System.out.print(array[0]+" ");//根取走
//最后一个放到根上
array[0]=array[n-1];
n--;
//重新调整
createHeap(array,n,0);
}
}
//需要完成一次建堆的过程
//n:表示堆中有多少个数据
//k:准备进行筛选的节点
public static void createHeap(int[] array,int n,int k){
int kLeft=2*k+1;//左孩子
int kRight=2*k+2;//右孩子
// if(key==array[k] || key==array[kLeft] || key==array[kRight]){
// 终止
// }
if(kLeft>=n && kRight>=n){//判断有没有子节点
return;
}
int kLeftValue=Integer.MAX_VALUE;
int kRightValue= Integer.MAX_VALUE;
if(kLeft<n){
kLeftValue=array[kLeft];
}
if(kRight<n){
kRightValue=array[kRight];
}
//从最上往下递归
// 三个节点开始比大小(假设这个堆以前就是满足要求的,即根不存在了)
if(array[k]<=kLeftValue && array[k]<=kRightValue){
return;
}
if(kLeftValue<kRightValue){//左子树的处理
int t=array[k];array[k]=array[kLeft];array[kLeft]=t;
createHeap(array,n,kLeft);
}else{//右子树的处理
int t=array[k];array[k]=array[kRight];array[kRight]=t;
createHeap(array,n,kRight);
}
}
