数据结构—八大排序

intellij

链接：https://pan.baidu.com/s/1ZcPuFQC2YirPt-QtKcEDmg?pwd=2314

提取码：2314

一、基数排序

适用于范围较小的整数数组，先统计每个元素出现的次数，然后根据统计结果依次输出原数组的每个元素。非比较排序。

package db;
import java.util.Arrays;
public class jspx {
    public static void main(String[] args) {
        int[] arr = {10, 2, 4, 9, 11, 15, 45, 87, 56, 23, 96, 100, 120, 17, 156};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr) {
        // 找最大值
        int max = arr[0];
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] > max) {
                max = arr[j];
            }
        } 
        // 找最大值的位数
        int maxLen = (max + "").length();   
        // 定义0-9十个桶
        int[][] bucket = new int[10][arr.length];
        // 定义桶记录工具
        int[] elementCount = new int[10]; // 每个桶中有效元素的计数
        int n = 1; // 每一轮所处理的位数（1, 10, 100,...）
        // 不断执行数据放入和数据取出
        for (int m = 0; m < maxLen; m++) {
            // 数据放入
            for (int i = 0; i < arr.length; i++) {
                // 将数据放入哪个桶
                int element = (arr[i] / n) % 10;
                // 将数据放入桶中，并更新元素计数
                bucket[element][elementCount[element]] = arr[i];
                elementCount[element]++;
            }  
            // 数据取出
            int index = 0;
            for (int k = 0; k < 10; k++) {
                for (int l = 0; l < elementCount[k]; l++) {
                    arr[index++] = bucket[k][l]; // 只增加 index
                }
                // 清除桶记录中的数据
                elementCount[k] = 0; // 计数清零
            }
            n = n * 10; // 处理下一个位数
        }
    }
}

二、冒泡排序 通过重复遍历待排序的数组，比较相邻的元素并交换它们的位置，如果顺序错误。每次遍历找到最大的元素放到最后，逐步将未排序的部分缩小，直到数组有序。

package db;

public class Bubble {
    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 5, 6, 8, 9, 7};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(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;
                }
            }
        }
    }
}

三、希尔排序

基于插入排序，通过将数组按一定增量分组，先对小组内元素进行插入排序，再逐步缩小增量，最终进行一轮插入排序，使得整个数组有序。

package db;

public class xepx {
	public static void main(String[] args) {
		int [] arr=new int [] {1,2,3,6,5,4,8,9,7
	};
		sort(arr);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]);
		}

}
public static void sort(int[] arr) {
	for(int h=arr.length/2;h>0;h/=2) {
		for(int i=h;i<arr.length;i++) {
			for(int j=i-h;j>0;j--) {
				if(arr[j]>arr[j+h]) {
					int temp=arr[j];
					arr[j]=arr[j+h];
					arr[j+h]=temp;
				}
			}
		}
	}
}
}

四、插入排序

将未排序的元素插入到已排序的部分中，逐步扩展已排序部分。开始时，将第一个元素视为已排序。对每个元素，从后向前遍历，找到合适的位置插入。

package db;

public class insert {
	public static void main(String[] args) {
		int[] arr=new int[] {1,2,3,4,5,8,4,2};
		sort(arr);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]);
		}
	}
	public static void sort(int[] arr) {
		for(int i=1;i<arr.length;i++) {
			for(int j=i-1;j>=0;j--) {
				if(arr[j]>arr[j+1]) {
					int temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
	}
}

五、堆排序

利用堆数据结构，把数组构造成一个最大堆或最小堆，然后依次将最大值或最小值取出放到已排序部分。该过程包括构建堆和调整堆。

package db;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = n-1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int rootIndex) {
        int largest = rootIndex; 
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;
        if (leftChild < n && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < n && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
        if (largest != rootIndex) {
            int swap = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}

六、快速排序

选择一个“基准”元素，将数组分为左右两个部分，左侧为小于基准的元素，右侧为大于基准的元素。递归地对这两个部分进行排序。

package db;
public class quiksort {
    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2};
        sort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void sort(int [] arr,int left,int right) {
        if (left>=right) {
            return ;
        }
        int i=left;
        int j=right;
        int base=arr[left];
        while(i!=j) {
            while(base<=arr[j]&&j>i) {
                j--;
            }
            while(base>=arr[i]&&i<j) {
                i++;
            }
            int t=arr[j];
            arr[j]=arr[i];
            arr[i]=t;
        }
        arr[left]=arr[j];
        arr[j]=base;
        sort(arr,left,i-1);
        sort(arr,i+1,right);
    }
}

七、选择排序

选择排序是一种简单的排序算法，其基本思路是通过多次遍历，将每次遍历中找到的最小（或最大）元素放到已排序序列的末尾（或开头）。

package db;

public class SeachSort {
   public static void main(String[] args) {
	   int [] arr=new int[] {1,2,5,6,8,9,7};
	   sort(arr);
	   for(int i=0;i<arr.length;i++) {
		   System.out.print(arr[i]);
	   }
   }
public static void sort(int[] arr) {
	for(int j=0;j<arr.length;j++) {
		int minIndex=j;
		int min=arr[j];
		for(int i=j+1;i<arr.length;i++) {
			if(min>arr[i] ){
				min=arr[i];
				minIndex=i;
			}
		}
		arr[minIndex]=arr[j];
		arr[j]=min;
	}
}
}

八、归并排序

采用分治法将数组分成两半，分别排序并合并。这是一个递归算法，先递归到最小的子数组（1个元素），再合并成有序数组。

package db;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2};
        sort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1) {
            arr[k++] = L[i++];
        }
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }
}