Java十大排序演算法怎麼實現
- 王林轉載
- 2023-05-15 15:55:061440瀏覽
排序演算法的穩定性：
假定在要排序的記錄序列中，存在多個具有相同的關鍵字的記錄，如果排序以後，保證這些記錄的相對次序保持不變，即在原序列中，a[i]=a[j]，且a[i] 在a[j] 之前，排序後保證a[i] 仍在a[j] 之前，則稱這種排序演算法是穩定的；否則稱為不穩定的。
一.選擇排序
每次從待排序的元素中選擇最小的元素，依序與第1、2、3...位置的元素進行交換。這樣在數組前面的部分形成有序區域。每進行一次交換，有序區長度加一。
public static void selectionSort(int[] arr){
//细节一：这里可以是arr.length也可以是arr.length-1
for (int i = 0; i < arr.length-1 ; i++) {
int mini = i;
for (int j = i+1; j < arr.length; j++) {
//切换条件，决定升序还是降序
if(arr[mini]>arr[j]) mini =j;
}
swap(arr,mini,i);
}
}二.冒泡排序
依序比較鄰近的兩個數，如果順序錯誤就把他們交換過來，這樣的話，每一輪比較下來都可以把最大的數放到它應該在的位置。 （就像是把最大的氣泡冒到最上層一樣）
這裡解釋順序錯誤的意義。我們依照升序排序，後面的值應該大於等於前面的值，如果不滿足的話，就交換。
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
//记录本次有没有进行交换的操作
boolean flag = false;
//保存在头就动头，保存在尾就动尾
for(int j =0 ; j < arr.length-1-i ; j++){
//升序降序选择地
if(arr[j] > arr[j+1])
{
swap(arr,j,j+1);
flag = true;
}
}
//如果本次没有进行交换操作，表示数据已经有序
if(!flag){break;} //程序结束
}
}三.插入排序
插入排序其實可以理解為我們玩撲克時摸牌的過程，我們在摸牌的時候手裡的牌總是有序的，每摸一張牌，就把這張牌插到它該在的位置。等所有的牌都摸完了以後，全部的牌就都有序了。
思考：在陣列前面形成了一個有序區域，那我查找目前數字應該插入位置的時候，用二分進行，是不是就可以把插入排序的複雜度優化到O(nlogn)了呀？
二分倒是指可以log的複雜度找到位置。關鍵在於如果用陣列儲存的話，插入的時候資料後移還是O(n)的複雜度。如果用鍊錶的話，找到位置插入是O(1)的了，但是鍊錶也沒辦法二分呀。
public static void insertSort(int[] arr){
//从第二个数开始，把每个数依次插入到指定的位置
for(int i = 1 ; i < arr.length ; i++)
{
int key = arr[i];
int j = i-1;
//大的后移操作
while(j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}四.希爾排序
希爾排序是Donald Shell於1959年提出的排序演算法，是直接插入排序的改進之後的高效版本。希爾排序需要準備一組資料作為增量序列。
這組資料需要滿足以下三個條件：
1. 資料遞減排列
2. 資料中的最大值小於待排序數組的長度
3. 資料中的最小值是1。
只要符合上述要求的陣列都可以作為增量序列，但不同的增量序列會影響到排序的效率。這裡我們用{5,3,1}作為增量序列來進行解說
實作最佳化的原因：減少資料量，使O(n)和O(n ^2)的差距並不大
public static void shellSort(int[] arr){
//分块处理
int gap = arr.length/2; //增量
while(1<=gap)
{
//插入排序：只不过是与增量位交换
for(int i = gap ; i < arr.length ; i++)
{
int key = arr[i];
int j = i-gap;
while(j >= 0 && arr[j] > key)
{
arr[j+gap] = arr[j];
j-=gap;
}
arr[j+gap] = key;
}
gap = gap/2;
}
}五.堆排序
是一棵完全二元樹，分為大根堆、小根堆兩種
可以O( 1)取最大/小值，可以O(logn)刪除最大/小值，可以O(logn)插入元素
MIN-HEAPIFY（i）操作：
我們假設完全二元樹中某節點i 的左子樹和右子樹都滿足小根堆的性質，假設i 節點的左孩子是left_i，i 節點的右孩子是rigℎt_i。那如果a[i] 大於a[left_i] 或a[rigℎt_i] 的話，那以i 節點為根節點的整棵子樹就不滿足小根堆的性質了，我們現在要進行一個操作：把以i 為根節點的這棵子樹調整成小根堆。
//堆排序
public static void heapSort(int[] arr){
//开始调整的位置为最后一个叶子节点
int start = (arr.length - 1)/2;
//从最后一个叶子节点开始遍历，调整二叉树
for (int i = start; i >= 0 ; i--){
maxHeap(arr, arr.length, i);
}
for (int i = arr.length - 1; i > 0; i--){
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}
//将二叉树调整为大顶堆
public static void maxHeap(int[] arr, int size, int index){
//建立左子节点
int leftNode = 2 * index + 1;
//建立右子节点
int rightNode = 2 * index + 2;
int maxNode = index;
//左子节点的值大于根节点时调整
if (leftNode < size && arr[leftNode] > arr[maxNode]){
maxNode = leftNode;
}
//右子节点的值大于根节点时调整
if (rightNode < size && arr[rightNode] > arr[maxNode]){
maxNode = rightNode;
}
if (maxNode != index){
int temp = arr[maxNode];
arr[maxNode] = arr[index];
arr[index] = temp;
//交换之后可能会破坏原来的结构，需要再次调整
//递归调用进行调整
maxHeap(arr, size, maxNode);
}
}我使用的是大根堆，排序的過程歸根下來就是：先左底根後右底根（看自己怎麼寫）->每個根向上在向下。 （左右上下）
六.歸併排序
歸併排序是分治法的典型應用，先來介紹一下分治法，分治法是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題規模很小可以直接求解，再將子問題的解合併得到原問題的解。
歸併排序分解子問題的過程就是每次將陣列分成2份，直到陣列的長度為1（因為只有一個數字的陣列是有順序的）。然後再將相鄰的有序數組合併成一個有序數組。直到全部合到一起，整個陣列就排序完畢了。現在要解決的問題就是如何把兩個有序的數字組合併成一個有序的數組。其實就是每次比較兩個陣列目前最小的兩個元素，哪個小就選哪個
陣列a |
陣列b |
說明 |
答案陣列 |
2,5 ,7 |
1,3,4 |
#1 | 1 |
2,5,7 |
1,3,4 |
2 |
#1,2 |
2,5,7 |
1,3,4 |
#3 |
1,2,3 |
2,5,7 |
#1,3,4 |
4 |
1,2, 3,4 |
2,5,7 |
#1,3,4 |
#陣列b中沒有元素了，取5 |
1,2,3,4,5 |
#2,5,7 |
1,3,4 |
#在陣列b中沒有元素了，取7 |
1,2,3,4,5,7 |
public static void mergeSort(int[] arr, int low, int high){
int middle = (high + low)/2;
if (low < high){
//递归排序左边
mergeSort(arr, low, middle);
//递归排序右边
mergeSort(arr, middle +1, high);
//将递归排序好的左右两边合并
merge(arr, low, middle, high);
}
}
public static void merge(int[] arr, int low, int middle, int high){
//存储归并后的临时数组
int[] temp = new int[high - low + 1];
int i = low;
int j = middle + 1;
//记录临时数组中存放数字的下标
int index = 0;
while (i <= middle && j <= high){
if (arr[i] < arr[j]){
temp[index] = arr[i];
i++;
} else {
temp[index] = arr[j];
j++;
}
index++;
}
//处理剩下的数据
while (j <= high){
temp[index] = arr[j];
j++;
index++;
}
while (i <= middle){
temp[index] = arr[i];
i++;
index++;
}
//将临时数组中的数据放回原来的数组
for (int k = 0; k < temp.length; ++k){
arr[k + low] = temp[k];
}
}七.快速排序
快速排序的工作原理是：从待排序数组中随便挑选一个数字作为基准数，把所有比它小的数字放在它的左边，所有比它大的数字放在它的右边。然后再对它左边的数组和右边的数组递归进行这样的操作。
全部操作完以后整个数组就是有序的了。 把所有比基准数小的数字放在它的左边，所有比基准数大的数字放在它的右边。这个操作，我们称为“划分”(Partition)。
//快速排序
public static void QuickSort1(int[] arr, int start, int end){
int low = start, high = end;
int temp;
if(start < end){
int guard = arr[start];
while(low != high){
while(high > low && arr[high] >= guard) high--;
while(low < high && arr[low] <= guard) low++;
if(low < high){
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}
arr[start] = arr[low];
arr[low] = guard;
QuickSort1(arr, start, low-1);
QuickSort1(arr, low+1, end);
}
}
//快速排序改进版(填坑法)
public static void QuickSort2(int[] arr, int start, int end){
int low = start, high = end;
if(start < end){
while(low != high){
int guard = arr[start];//哨兵元素
while(high > low && arr[high] >= guard) high--;
arr[low] = arr[high];
while(low < high && arr[low] <= guard) low++;
arr[high] = arr[low];
}
arr[low] = guard;
QuickSort2(arr, start, low-1);
QuickSort2(arr, low+1, end);
}
}八.鸽巢排序
计算一下每一个数出现了多少次。举一个例子，比如待排序的数据中1出现了2次，2出现了0次，3出现了3次，4出现了1次，那么排好序的结果就是{1.1.3.3.3.4}。
//鸽巢排序
public static void PigeonholeSort(int[] arr){
//获取最大值
int k = 0;
for (int i = 0; i < arr.length; i++) {
k = Math.max(k,arr[i]);
}
//创建计数数组并且初始化为0
int[] cnt = new int[k+10];
for(int i = 0 ; i <= k ; i++) { cnt[i]=0; }
for(int i = 0 ; i < arr.length ;i++) { cnt[arr[i]]++; }
int j = 0;
for(int i = 0 ; i <=k ; i++)
{
while(cnt[i]!=0)
{
arr[j]=i;
j++;
cnt[i]--;
}
}
}鸽巢排序其实算不上是真正意义上的排序算法，它的局限性很大。只能对纯整数数组进行排序，举个例子，如果我们需要按学生的成绩进行排序。是一个学生+分数的结构那就不能排序了。
九.计数排序
先考虑这样一个事情：如果对于待排序数据中的任意一个元素 a[i]，我们知道有 m 个元素比它小，那么我们是不是就可以知道排好序以后这个元素应该在哪个位置了呢？（这里先假设数据中没有相等的元素）。计数排序主要就是依赖这个原理来实现的。
比如待排序数据是{2,4,0,2,4} 先和鸽巢一样做一个cnt数组{1,0,2,0,2} 0,1,2,3,4
此时cnt[i]表示数据i出现了多少次，
然后对cnt数组做一个前缀和{1,1,3,3,5} ：0,1,2,3,4
此时cnt[i]表示数据中小于等于i的数字有多少个
待排序数组 |
计数数组 |
说明 |
答案数组ans |
2,4,0,2,4 |
1,1,3,3,5 |
初始状态 |
null,null,null,null,null, |
2,4,0,2,4 |
1,1,3,3,5 |
cnt[4]=5，ans第5位赋值，cnt[4]-=1 |
null,null,null,null,4 |
2,4,0,2,4 |
1,1,3,3,4 |
cnt[2]=3，ans第3位赋值，cnt[2]-=1 |
null,null,2 null,4 |
2,4,0,2,4 |
1,1,2,3,4 |
cnt[0]=1，ans第1位赋值，cnt[0]-=1 |
0,null,2,null,4 |
2,4,0,2,4 |
0,1,2,3,4 |
cnt[4]=4，ans第4位赋值，cnt[4]-=1 |
0,null,2,4,4 |
2,4,0,2,4 |
0,1,2,3,3 |
cnt[2]=2，ans第2位赋值，cnt[2]-=1 |
0,2,2,4,4 |
十.基数排序
基数排序是通过不停的收集和分配来对数据进行排序的。
因为是10进制数，所以我们准备十个桶来存分配的数。
最大的数据是3位数，所以我们只需要进行3次收集和分配。
需要先从低位开始收集和分配（不可从高位开始排，如果从高位开始排的话，高位排好的顺序会在排低位的时候被打乱，有兴趣的话自己手写模拟一下试试就可以了）
在收集和分配的过程中，不要打乱已经排好的相对位置
比如按十位分配的时候，152和155这两个数的10位都是5，并且分配之前152在155的前面，那么收集的时候152还是要放在155之前的。
//基数排序
public static void radixSort(int[] array) {
//基数排序
//首先确定排序的趟数;
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int time = 0;
//判断位数;
while (max > 0) {
max /= 10;
time++;
}
//建立10个队列;
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
//进行time次分配和收集;
for (int i = 0; i < time; i++) {
//分配数组元素;
for (int j = 0; j < array.length; j++) {
//得到数字的第time+1位数;
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count = 0;//元素计数器;
//收集队列元素;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue3 = queue.get(k);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}以上是Java十大排序演算法怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！