ssss其实早在一年前，对于八大算法就能1个多小时全部复现出来，起初没觉得有什么，但什么随着力扣刷题，发现八大排序算法越来越重要，因此，我觉得有必要对其进行总结，或许已经有很多人对其总结了，不过总是不如自己亲身经历一遍，再复现一遍，算法重要，思维更重要。
ssss排序的分类：
ssdssss①、内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序
sdsssss②、外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序
ssss而我们所说的方法，都是内部方法。
ssss算法的复杂度：时间复杂度，空间复杂度。
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 归并排序
- 堆排序
- 基数排序(桶排序)
ssss基本思想：对排序序列进行从前向后（下标较小的开始），依次比较相邻元素的值，若逆序则交换，则值较大的元素逐渐从前移向后，就像水底的气泡。每一轮的排序都是找到一个最大值，放到最后面，就和气泡浮出水面一样，一共需要执行N-1轮
ssss在每一轮过程中，都会比较相邻的大小，如果在某一轮发现都没有进行变化，则表明已经排序好了，所以不需要再继续下去。
sssseg：[35,88,16,27,32,4,90,56,79]
ssasdasdasddsdasdss
package com.wwj.sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args){
int[] arr = new int[]{35,88,16,27,32,4,90,56,79};
int tmp; //中间变量
boolean flag = false; //标识变量，标识是否进行过交换
for(int i =0 ; i< arr.length-1 ; i++){
for(int j=0 ; j arr[j+1]){
flag = true;
tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
//优化
if(!flag) //说明依次交换：一次都没有发生过
break;
else
flag = false; //重置flag！！！，让起进行第二轮的判断，否则就起不到优化的作用了
}
System.out.println(Arrays.toString(arr));
}
}
==================================================================================================================
结果：[4, 16, 27, 32, 35, 56, 79, 88, 90]
选择排序
ssss基本思想：其实和冒泡排序差不多，冒泡排序是一轮一轮的相邻两个进行比较，每一轮可以比较出一个最大值，然后一共要执行N-1次，再次可以通过设置flag,用if语句进行判断。而选择排序是设置一个最小值，一般是初始值设为最小值，然后和所有数值进行比较，找出最小的数值放在第一位，然后依次执行N-1次，每一次比较的元素依次递（可以排成从大到小，也可 以排成从小到大）。
ssasdasddasdd
sssseg：[103，34，119，1]
ssdsdsdsdsdsdss
public class selectSort {
public static void main(String[] args) {
int[] arr = new int[]{103,34,119,1};
int minIdx;
int minVal;
for(int i=0 ; i< arr.length-1 ; i++){
minIdx = i;
minVal = arr[i];
for(int j=i+1 ; j< arr.length; j++){
if(minVal>arr[j]){ //记录最大值的下标和值
minIdx = j;
minVal = arr[j];
}
}
if(minIdx != i){
arr[minIdx] = arr[i];
arr[i] = minVal;
}
}
System.out.println(Arrays.toString(arr));
}
}
==============================================================================================
结果：[1, 34, 103, 119]
插入排序
ssss基本思想：将一个数组的元素分成一个有序数组，和无序数组，然后将无序数组的数值依次 和有序数组中得数组（也就是第一个数）进行比较，然后放入到有序数组中，最后也要 执行N-1次。
sssseg：[17，3，25，14，20，9]
public class insertSort {
public static void main(String[] args) {
int[] arr = new int[]{17,3,25,14,20,9};
int insertIdx;
int insertVal;
for(int i=1 ; i=0 && insertVal < arr[insertIdx]){
arr[insertIdx+1] = arr[insertIdx];
insertIdx--;
}
arr[insertIdx+1] = insertVal;
}
System.out.println(Arrays.toString(arr));
}
}
============================================================================================================
结果：[3, 9, 14, 17, 20, 25]
希尔排序
ssss本质：实际上也是一种插入排序，只不过在一个序列中，如果较小得在后面，通过插入排序效率并不高，针对这种情况，提出了希尔排序。
ssss基本思想：首先通过一组元素得基本个数，让其除以2，算出第一次排序得增量是多少，然后分成几个组，对各组进行排序.一直持续到增量为1时结束。而对各组进行排序，我们可以通过交换排序，也可以通过希尔排序，每种排序针对不同得情况。
sssseg：[8，9，1，7，2，3，5，4，6，0]
sadasdasdasdsdasdsadasds
ssss①、希尔+交换
public class shellSort {
public static void main(String[] args) {
int[] arr= new int[]{8,9,1,7,2,3,5,4,6,0};
int temp;
//1、我们首先要进行分组，然后每组比较，一直分到增量为1时，就结束
for(int gap = arr.length/2 ; gap>0 ; gap/=2 ){ //增量大小，最大为序列长度的1/2，最小为1，逐半减小
for(int i = gap ; i=0 ; j-=gap){ //每次和同组的比较也就是前gap个
if(arr[j]>arr[j+gap]){
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
}
System.out.println("希尔排序和交换排序后的序列为："+ Arrays.toString(arr));
}
}
===============================================================================================
结果：希尔排序和交换排序后的序列为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ssss②、希尔+插入
public class shellSort {
public static void main(String[] args) {
int[] arr= new int[]{8,9,1,7,2,3,5,4,6,0};
int temp;
//分组
for(int gap = arr.length/2 ; gap>0 ; gap/=2){
for(int i=gap ; i=0 && insertVal
快速排序
ssss本质：是对冒泡排序的一种改进
ssss基本思想：首先我们要找到他中间索引的值，然后以此分成两个序列，通过编程使左边比右边的数小，然后让两别分别进行递归，这样就达到了排序的效果。
ssss注意：通过while循环找出两边序列各自不符合条件的值，然后交换，但是要考虑：
sdssss1、如果两边全部满足条件呢dsssss2、如果两边有与中间值相等的呢
sssseg：[2,10,8,22,34,5,12,28,21,11]
sdsdsdsssss
public class quickSort {
public static void main(String[] args) {
int[] arr = new int[]{2,10,8,22,34,5,21,21,21,11};
quickSort(arr, 0 , arr.length-1);
System.out.println("快速排序"+ Arrays.toString(arr));
}
private static void quickSort(int[] arr ,int left , int right ){ //left，right分别代表序列左右两边的值
int l = left;
int r = right;
int pivot = arr[(l+r)/2]; //中轴值
int tmp; //中间值
//首先我们要以中轴值为界，把序列分成两份，保证左边的序列的数值比右边的序列的数值大
//首先一个死循环
while (lpivot) r--; // 以中轴值为界
if(l>r) break; //如果当l>r时，说明此时左边序列的数字小于右边数列的值
tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp; //进行互换，但是要注意，前面两个while循环，都取的是<>号，如果是==呢，此时需要改变l,r的值
if(arr[l] == pivot) l++;//交换完后，如果左边相等，我们要让l++,原因：1、以便让后面进行递归，2、退出while循环
if(arr[r] == pivot) r--;//交换完成后，如果右边相等，我们要让r--，以便让后面进行递归 2、退出whil循环 }
}
//如果是根据后面两个if语句退出的while循环，说明r==f,此时我们为了后面的遍历要r++,f--
if(r==l){ r+=1;l-=1; }
//向左递归,但是要判别下最左边的下标小于leftf
if(right>l) quickSort(arr,l,right);
}
}
===============================================================================================
结果快速排序[2, 5, 8, 10, 11, 21, 21, 21, 22, 34]
归并排序
ssss核心思想就是“分治”，“分”的情况比较简单，最后拆成一个元素的序列，“治”的情况比较麻烦，合的时候需要把他们一次一次递归，然后排列。核心为“治”，一共要合并N-1次（N为长度）
ssss分成三个阶段：1、分 2、合 3、复制
sssseg：[2,10,8,22,34,5,21,21,21,11]
public class MergeSort {
public static void main(String[] args) {
int arr[] = { 2,10,8,22,34,5,21,21,21,11 };
int[] tmp = new int[arr.length];
mergeSort(arr,0,arr.length-1 , tmp);
System.out.println("归并排序的顺序："+Arrays.toString(arr));
}
private static void mergeSort(int[] arr , int left , int right , int[] tmp){
if(left
堆排序
ssss基本思想：堆排序分析的比较好的文章
//堆排序
public static void heapSort(int[] arr) {
//构造大根堆
heapInsert(arr);
int size = arr.length;
while (size > 1) {
//固定最大值
swap(arr, 0, size - 1);
size--;
//构造大根堆
heapify(arr, 0, size);
}
}
//构造大根堆（通过新插入的数上升）
public static void heapInsert(int[] arr) {
for (int i = 0; i < arr.length; i++) {
//当前插入的索引
int currentIndex = i;
//父结点索引
int fatherIndex = (currentIndex - 1) / 2;
//如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
//然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
while (arr[currentIndex] > arr[fatherIndex]) {
//交换当前结点与父结点的值
swap(arr, currentIndex, fatherIndex);
//将当前索引指向父索引
currentIndex = fatherIndex;
//重新计算当前索引的父索引
fatherIndex = (currentIndex - 1) / 2;
}
}
}
//将剩余的数构造成大根堆（通过顶端的数下降）
public static void heapify(int[] arr, int index, int size) {
int left = 2 * index + 1;
int right = 2 * index + 2;
while (left < size) {
int largestIndex;
//判断孩子中较大的值的索引（要确保右孩子在size范围之内）
if (arr[left] < arr[right] && right < size) {
largestIndex = right;
} else {
largestIndex = left;
}
//比较父结点的值与孩子中较大的值，并确定最大值的索引
if (arr[index] > arr[largestIndex]) {
largestIndex = index;
}
//如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
if (index == largestIndex) {
break;
}
//父结点不是最大值，与孩子中较大的值交换
swap(arr, largestIndex, index);
//将索引指向孩子中较大的值的索引
index = largestIndex;
//重新计算交换之后的孩子的索引
left = 2 * index + 1;
right = 2 * index + 2;
}
}
//交换数组中两个元素的值
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
基数排序(桶排序)
ssss之所以叫做桶排序，是因为分成了10个桶，0-9，这样我们可以从这个序列的各个数值的个位开始放入桶中，然后按顺序取出，组成新出的数组，再按照十位……依次类推，需要执行的次数，就是序列中最大数的位数。
ssss基数排序是空间换时间的经典算法
ssss相同的数值排序本来在前面的排序后也在前面
public class RadixSort {
public static void main(String[] args) {
int[] arr = { 53, 3, 542, 748, 14, 214};
radixSort1(arr); //整体
System.out.println(Arrays.toString(arr));
}
//基数排序，俗称桶排序，基本思想就是：按照个位，十位，百位等分别放入对应得桶中，
// 然后依次进行排序，所以我们首先要找到一个数组中的最大值，然后用二维数组表达出桶，以及里面对应的数
private static void radixSort1(int[] arr) {
int max = arr[0]; //假定第一个数是最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大数是几位数
int maxLength = (max + "").length();
//10 对应0-9. arr.length对应着我们要排序的数组的元素个数，防止溢出
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10]; //存入的是特定位是0~9的个数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
//(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
for (int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j];
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有数据，我们才放入到原数组
if (bucketElementCounts[k] != 0) {
//循环该桶即第k个桶(即第k个一维数组), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第" + (i + 1) + "轮，对个/十/百/...位的排序处理 arr =" + Arrays.toString(arr));
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）