这篇文章有点长,我把常用的排序算法做了一下总结,可以马下来有时间慢慢看,希望能有所帮助.
我们来回顾一下常用的排序算法,在所有排序算法中,常用的有八大内部排序.分别是冒泡排序,选择排序,快速排序,并归排序,链式基数排序,插入排序,希尔排序和堆排序
image.png
我们按照顺序,一一回顾这些算法的思路,应用场景以及算法的代码
首先是冒泡排序
1.冒泡排序
思路:从第一个数据开始,将顺序表中的每一个数据数据,与他的后一个数据比较大小,如果比后一个大,就交换位置,直到倒数第二个数与倒数第一个数比较完毕,我们得到最大的一个数,放在队尾.以此类推,我们每进行一轮比较,就可以得到剩下的数据中最大的数.直到所有的数都不用交换位置时,我们得到一个从小到大的有序数列.
应用场景:8个以内的数据,排序最快
代码:
private void bubbleSort(int[] array){
for (int j = array.length - 1; j > 0; j--) {
boolean flag = true;
for (int i = 0; i < j; i++) {
//从0开始,直到array.length-1,每一个与后一个比较
if (array[i]>array[i+1]){
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
flag = false;//如果有交换,证明还没有排好
}
}
if (flag){
return;
}
}
}
@Test
public void test22(){
int[] array = new int[]{
3,5,8,1,4,7,2,6
};
bubbleSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
2.选择排序
思路:选择数列中下标为0的数作为index,将他后面的数依次与index指向的数比较,若后面的数比index指向的数小,就把index指向后边的数,直到比较到数列尾,此时,我们可以确定index所指向的数是数列中最小的数,我们把他与下标为0的数交换位置,然后,我们将下标为1的数作为index,继续选择排序,直到我们将数列length-1的数作为index,比较完后,得到数列为从小到大的有序数列.
适用场景:8个以内的数,排序最快
代码:
private void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int index = i;
for (int j = i + 1; j < array.length; j++) {
//如果后面的数比array[i]小,就将index指向后面较小的数
if (array[j] < array[index]) {
index = j;
}
}
//一轮比较完后,将最小的数放到队列前面
if (index != i) {
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
@Test
public void test22() {
int[] array = new int[]{
3, 5, 8, 1, 4, 7, 2, 6
};
selectSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
冒泡排序和选择排序在之前介绍线性表的顺序存储结构时有讲到
3.快速排序
思路:在数列中选择一个数作为基准,用其他数与该数比较,比他大的放在他的右边,比他小就放在左边,这样一轮比较完成后,该数左边都比他小,右边都比他大.然后我们以该数为中间点,可以将数列分成两部分,这两部分进行同样的操作,以此类推,直到数列有序
那么,如何将比这个数大的放在其右边,比他小的放在他左边呢?
我们定义两个指针,分别指向数列的头和尾,尾指针从尾部向头部移动,若尾指针指向的数比该数大,不用理会,若比他小,就把尾指针指向的数与头指针指向的数交换位置,这样就可以保证尾指针后面的数都是比目标数大.
头指针则相反,从头部向尾部移动,若头指针指向的数比目标数小,不用理会,若比他大,就将头指针与尾指针指向的数交换位置.这样就可以保证头指针之前的数,都比该数小.直到头指针与尾指针重合时,就可以得到目标数的位置.而目标数左边的数就是头指针前面的数,肯定比目标数小.同理右边的数就是尾指针后面的数,肯定比他大.
image.png
应用场景:数据量大并且是线性结构
代码:
/**
* @param array 目标数组
* @param begain 快排起点
* @param end 快排终点
*/
private void quickSort3(int[] array, int begain, int end) {
if (end - begain <= 0) {
return;
}
int low = begain;//头指针
int height = end;//尾指针
int x = array[begain];//目标数,即,目标是该数右边的数都比他大,左边的数都比他小
boolean direction = true;//头指针和尾指针移动的标识
L1:
while (low < height) {
//我们先移动尾指针,尾指针向前移动
if (direction) {
for (int i = height; i > low; i--) {
if (array[i] < x) {
//交换位置
int temp = array[i];
array[i] = array[low];
array[low] = temp;
//给尾指针赋值
height = i;
//开始移动头指针
direction = !direction;
continue L1;
}
}
//如果一直没有进入条件,也要给尾指针赋值
height = low;
} else {
//移动头指针,头指针从前向后移动
for (int i = low; i < height; i++) {
if (array[i] > x) {
//交换位置
int temp = array[i];
array[i] = array[height];
array[height] = temp;
//给头指针赋值
low = i;
//开始移动尾指针
direction = !direction;
continue L1;
}
}
//如果一直没有进入条件,也要给头指针赋值
low = height;
}
}
//当头指针与尾指针重合,此时,x的位置已经确定,即头指针的位置
array[low] = x;
//然后以low为界,分为新的两组数列,执行快排算法.这里类似二叉树的前序遍历
quickSort(array, begain, low - 1);
quickSort(array, low + 1, end);
}
@Test
public void test22() {
int[] array = new int[]{1, 7, 4, 9, 3, 2, 6, 5, 8};
quickSort(array, 0, array.length - 1);
for (int i : array) {
System.out.print(i + " ");
}
}
快排在前面的文章中也有讲到分治法和快排
4.归并排序
思想:
如下图,将一个数列从中间分为两个有序的数列,然后再将两个数列按照从小到大的顺序合并成一个有序数列.
image.png
那么问题来了,
- 随机的一个数列,从中间分成两个数列,我们不能保证这两个数列是有序的.
- 怎样将这两个有序数列合并成一个有序数列呢?
解答:
- 这个问题很简简单,如下图,我们将数列不断地细分,直到每个数列中只有一个数,这样就可以的到两个有序的数列.
image.png
-
怎样将两个有序的数列合并成呢?
还是看这张图,我们将左右两边的数列,从第一个开始比大小,将小的放在目标数组,然后取下一个继续比较,直到左右两边有一边数据用完,将剩下的数据放入目标数组.完成合并.
image.png
具体分析:
我们用一个新的数组result[]来存储合并后的数列,用3个i=0,j=0,k=0指针分别表示leftArray[],rightArray[]和result[]的下标.
首先leftArray[i]跟rightArray[j]比大小,
若leftArray[i]<rightArray[j],result[k] = leftArray[i]. i++,k++.
若leftArray[i]>rightArray[j],result[k] = rightArray[j],j++,k++.
即,把较小的放入目标数组,然后比较下一个.
直到有一个数列数据用完,算法结束
左边数据用完,将右边数据全部放进结果数组
while(i>leftArray.length){
result[k] = rightArray[j];j++;k++;
}
右边数据用完,将左边数据全部放进目标数组
while(j>rightArray.length){
result[k] = leftArray[i];i++;k++.
}
适用场景:数据量大并且有很多重复数据,链式结构
代码:
/**
* @param array 需要排序的目标数组
* @param left 排序的起点
* @param right 排序的终点
*/
private void mergeSort(int[] array, int left, int right) {
if (left >= right) {
//直到左右数列分成只有一个数据时,开始合并操作
return;
} else {
int mid = (left + right) / 2;
//这里类似于二叉树的后序遍历
mergeSort(array, left, mid);//分左边数组
mergeSort(array, mid + 1, right);//分右边数组
merge(array, left, mid + 1, right);//合并操作
}
}
/**
* 合并操作
*
* @param array 目标数组
* @param left 左
* @param mid 中
* @param right 右
*/
private void merge(int[] array, int left, int mid, int right) {
//创建左右数组
int leftSize = mid - left;
int rightSize = right - mid + 1;//将mid位置的数据包含在rightArray中
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++;
}
}
@Test
public void testMergeSort(){
int[] array=new int[]{2,1,6,4,3,9,8,10,7,5};
mergeSort(array,0,array.length-1);
for (int i : array) {
System.out.print(i+" ");
}
}
5.链式基数排序
image.png
思想:比如上图麻将的排序,先按照点数大小排成一个链表,然后根据类别,分成3个链表,分别按照大小顺序存放不同类别的麻将,最后将这3个链表连接起来,得到最终的排好序的麻将结果链表.
使用场景:多关键字排序
代码:
package com.example.jett.lsn_2.mahjong;
/**
* Created by 48608 on 2017/12/6.
*/
public class Mahjong {
public int suit;//筒，万，索
public int rank;//点数 一 二 三
public Mahjong(int suit, int rank) {
this.suit = suit;
this.rank = rank;
}
@Override
public String toString() {
return "("+this.suit+" "+this.rank+")";
}
}
package com.example.jett.lsn_2.mahjong;
import java.util.LinkedList;
/**
* Created by Jett on 2018/11/28.
*/
public class Test {
@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);
}
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();
//放到组中
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]);
}
}
}
链式基数排序在前面的文章也有讲过
6.插入排序
image.png
思想:如上图,从数列第一个数开始,将他与他前面的数进行比较,如果比前面的数小,就插入到前面的位置,直到比较到第0个数到达数列头部
使用场景:打牌摸排时的场景
代码:
/**
*
* @param array 目标数组
*/
private void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {//从第一位开始
int j = i;
int target = array[j];
while (j>0 && target<array[j-1]){//与前一位比较,直到数组头部
array[j] = array[j-1];//比前一位小时,将前一位向后移,留出空位置方target
j--;//继续与前一位比较,直到数组头部
}
array[j] = target;//比较完之后,将target插入到预留的位置
}
}
@Test
public void insertSortTest(){
int[] array=new int[]{2,3,4,5,6,7,1,8,9};
insertSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
7.希尔排序
image.png
思想:
跟插入排序类似,我们只是将插入排序的步长由1变为n
如上图,第一次将步长定义为6,得到6组排好序的数列
第二次在第一次基础上,步长为3,得到3组排好序的数列.
最后将步长定义为1,得到1组排好序的数列
适用场景:
麻将在玩的过程中的重复排序（因为数据源本身即是有序）
合适数据量中等情况，几十个到几万个
代码:
private void shellSort(int[] array, int step) {
for (int k = 0; k < step; k++) {
for (int i = k + step; i < array.length; i += step) {
int j = i;
int target = array[j];
while (j > step - 1 && target < array[j - step]) {
array[j] = array[j - step];
j -= step;
}
array[j] = target;
}
}
}
@Test
public void shellSortTest() {
int[] array = new int[]{2, 3, 4, 5, 6, 7, 1, 8, 9};
shellSort(array, 3);
shellSort(array, 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
8.堆排序
image.png
思想:
将数组中的数据存放到堆中,数组的下标满足这样的关系
child = parent*2+1.
堆排序的过程：
- 从最后一个非叶子节点开始，每三个节点做一次大小比较，最小的做根
移动过程中如果子树上的顺序被破坏了，子树上重新调整三个节点的位置 - 取走整个树的根节点，把最后一个叶子做为根节点
- 重复1和2，直到所有节点被取走了
@Test
public void test(){
int[] array=new int[]{2,3,4,5,6,7,1,8,9};
heapSort(array,array.length);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
/**
* 调整堆
*/
void maxHeapify(int array[],int start,int end){
//父亲的位置
int dad=start;
//儿子的位置
int son=dad*2+1;
while(son<=end){//如果子节点下标在可以调整的范围内就一直调整下去
//如果没有右孩子就不用比,有的话,比较两个儿子，选择最大的出来
if(son+1 <= end && array[son]<array[son+1]){
son++;
}
//和父节点比大小
if(array[dad]>array[son]){
return;
}else{//父亲比儿子小，就要对整个子树进行调整
int temp=array[son];
array[son]=array[dad];
array[dad]=temp;
//递归下一层
dad=son;
son=dad*2+1;
}
}
}
void heapSort(int array[],int len){
//建堆 len/2-1最后一个非叶子节点
for(int i=len/2-1;i>=0;i--){
maxHeapify(array,i,len-1);
}
//排序,根节点和最后一个节点交换
//换完以后，取走根，重新建堆
//len-1 最后一个节点
for(int i=len-1;i>0;i--){
int temp=array[0];
array[0]=array[i];
array[i]=temp;
maxHeapify(array,0,i-1);
}
}
网友评论