排序算法的分类1.冒泡排序2.选择排序3.插入排序4.希尔排序5.快速排序6.归并排序7.基数排序8.堆排序
排序算法的分类- 内部排序:
指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。外部排序法：
数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。
3.常见的排序算法分类
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
public class BubbleSort {
public static void main(String[] args) {
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = (int) (Math.random() * 100);
}
System.out.println("排序前：" + Arrays.toString(a));
//冒泡排序
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {//完成几次外层循环，最后就几位有序，故内存循环要减去外层循环的次数
if (a[j] > a[j + 1]) {//利用中间值temp交换
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
System.out.println("排序后：" + Arrays.toString(a));
}
}
2.选择排序
基本思想：从全部数中选出最小（大）值，与第一位交换，继续从剩余数选出最小(大)值，与第二位交换····以此类推，直到n-1位。
思路分析图：
public class SelectSort {
public static void main(String[] args) {
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = (int) (Math.random() * 100);
}
System.out.println("排序前：" + Arrays.toString(a));
for (int i = 0; i < a.length - 1; i++) {//选择次数n-1
int min = a[i];//假定该数最小
int minIndex = i;
for (int j = i + 1; j < a.length; j++) {//找出最小数及其下标
if (min > a[j]) {
min = a[j];
minIndex = j;
}
}
if (minIndex != i) {//交换
a[minIndex] = a[i];
a[i] = min;
}
}
System.out.println(Arrays.toString(a));
}
}
3.插入排序
基本思想是：假设将数组分成两部分：有序部分和无序部分，最开始有序部分只有第一位数字，其余为无序部分数字。从无序部分中拿出第一位数字与有序表数字比较，若拿出数字较小，则与之比较的数字后移，直至拿出的数大于比较的数，则放在它的后一位上。以此类推直到全部放入有序表
public class InsertSort {
public static void main(String[] args) {
int[] a=new int[10];
for(int i=0;i<10;i++){
a[i]=(int)(Math.random()*100);
}
System.out.println(Arrays.toString(a));
System.out.println("=======");
insertSort(a);
System.out.println(Arrays.toString(a));
}
public static void insertSort(int[] arr){
for(int i=1;i=0 && insertVal
4.希尔排序
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
希尔排序法基本思想
希尔排序是把记录按下标的一定增量进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1 时，整个文件恰被分成一组，算法便终止
public class ShellSort {
public static void main(String[] args) {
int[] a=new int[10];
for(int i=0;i<10;i++){
a[i]=(int)(Math.random()*100);
}
// int[] a={5,2,4,3,1,6,55,8} ;
System.out.println(Arrays.toString(a));
ShellSort(a);
}
public static void ShellSort(int[] arr){
for(int gap=arr.length/2;gap>0;gap/=2){//分组，组数为gap，增量也为gap，直至增量（组数）为一
for(int i=gap;i=0;j-=gap){
if(arr[j]>arr[j+gap]){
int temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
}
5.快速排序
public class QuickSort {
public static void main(String[] args) {
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = (int) (Math.random() * 100);
}
// int[] a = {3, 1, 7, 1, -2, -3, 4};
System.out.println("排序前：" + Arrays.toString(a));
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
//快排代码
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int pivot = arr[(left + right) / 2];
int temp = 0;
while (l < r) {
while (arr[l] < pivot) {
l++;
}
while (arr[r] > pivot) {
r--;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == pivot) {
r--;
}
if (arr[r] == pivot) {
l++;
}
}
if (l == r) {
l++;
r--;
}
if (right > l) {
quickSort(arr, l, right);
}
if (left < r) {
quickSort(arr, left, r);
}
}
}
6.归并排序
public class MergeSort {
public static void main(String[] args) {
int[] a=new int[10];
for(int i=0;i
7.基数排序
public class RadixSort {
public static void main(String[] args) {
int[] a=new int[10];
for(int i=0;i
8.堆排序
public class HeapSort {
public static void main(String[] args) {
int arr[]={4,6,8,5,9,11,14,3,1};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
//堆排序的方法
public static void heapSort(int[] arr) {
int temp=0;
System.out.println("堆排序");
for(int i=arr.length/2-1;i>=0;i--){//构成大顶堆
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--){
temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;//最大的已经放到最后
adjustHeap(arr,0,j);//调整剩余的重新满足大顶推结构，已经调整的最后一个不再参与重新调整成大顶堆结果（每调整一个j--）
}
}
//数组（二叉树）调节成大顶堆
//方法注释快捷键" /** + enter "
/**
*
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从最后一个非叶子节点开始
if (k + 1 < length && arr[k] < arr[k + 1]) {//获取该非叶子节点的较大子节点
k++;
}
if (arr[k] > temp) {//较大子节点大于自身，则将该较大子节点赋予该节点，同时下标i转成下标k
arr[i] = arr[k];
i = k;//作用？？
} else {
break;
}
}
arr[i]=temp;
}
}
