摘要:冒泡排序插入排序選擇排序堆排序父節(jié)點(diǎn)索引尾節(jié)點(diǎn)索引歸并排序快速排序附錄交換方法基于策略模式的主程序?qū)崿F(xiàn)定義一個(gè)數(shù)組構(gòu)造函數(shù)初始化數(shù)組遍歷數(shù)組中每一個(gè)元素展示
</>復(fù)制代碼
「博客搬家」 原地址: 簡(jiǎn)書 原發(fā)表時(shí)間: 2017-08-17
網(wǎng)上有很多排序算法的總結(jié),不過有很多缺點(diǎn),比如有些根本就是錯(cuò)的,無法通過測(cè)試用例,有些過于冗長(zhǎng)。所以我總結(jié)了一套短小精悍的 Java 實(shí)現(xiàn),經(jīng)測(cè)試,該套實(shí)現(xiàn)可通過牛客網(wǎng)的關(guān)于此的所有測(cè)試用例。
1. 冒泡排序</>復(fù)制代碼
public class BubbleSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
}
2. 插入排序
</>復(fù)制代碼
public class InsertSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 1; i < size; i++) {
int temp = a[i];
int j = i;
while (j > 0 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
}
3. 選擇排序
</>復(fù)制代碼
public class SelectSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 0; i < size - 1; i++) {
int min = i;
for (int j = i + 1; j < size; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
swap(a, i, min);
}
}
}
}
4. 堆排序
</>復(fù)制代碼
public class HeapSort implements KySort {
public void kySort(int[] a, int n) {
for (int i = n / 2; i >= 0; i--) {
heapAdjust(a, i, n - 1);
}
for (int i = n - 1; i > 0; i--) {
swap(a, 0, i);
heapAdjust(a, 0, i - 1);
}
}
/**
* @param index 父節(jié)點(diǎn)索引
* @param n 尾節(jié)點(diǎn)索引
*/
private void heapAdjust(int[] a, int index, int n) {
int temp = a[index];
for (int child = index * 2 + 1; child <= n; child = index * 2 + 1) {
if (child < n && a[child] < a[child + 1]) {
child++;
}
if (temp > a[child]) break;
a[index] = a[child];
index = child;
}
a[index] = temp;
}
}
5. 歸并排序
</>復(fù)制代碼
public class MergeSort implements KySort {
public void kySort(int[] a, int size) {
sort(a, 0, size - 1, new int[a.length]);
}
private void sort(int[] a, int left, int right, int[] temp) {
if (left >= right) return;
int mid = (left + right) / 2;
sort(a, left, mid, temp);
sort(a, mid + 1, right, temp);
merge(a, left, mid, right, temp);
}
private void merge(int[] a, int left, int mid, int right, int[] temp) {
int k = left;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= right) {
temp[k++] = a[j++];
}
while (left <= right) {
a[left] = temp[left];
left++;
}
}
}
6. 快速排序
</>復(fù)制代碼
public class QuickSort implements KySort {
@Override
public void kySort(int[] a, int size) {
quickSort(a, 0, size - 1);
}
private void quickSort(int[] a, int left, int right) {
if (right - left < 2) {
if (a[left] > a[right])
swap(a, left, right);
return;
}
int p = middleBy3(a, left, right);
quickSort(a, left, p - 1);
quickSort(a, p + 1, right);
}
private int middleBy3(int[] a, int left, int right) {
int p = (left + right) / 2;
int end = right;
if (a[left] > a[p]) swap(a, left, p);
if (a[left] > a[right]) swap(a, left, right);
if (a[p] > a[right]) swap(a, p, right);
int temp = a[p];
swap(a, p, right);
while (true) {
while (a[++left] < temp) ;
while (a[--right] > temp) ;
if (left >= right) break;
else swap(a, left, right);
}
swap(a, left, end);
return left;
}
}
7. 附錄
7.1 交換方法
</>復(fù)制代碼
public class Util {
public static void swap(int[] a, int i, int j) {
int k = a[i];
a[i] = a[j];
a[j] = k;
}
}
7.2 基于策略模式的主程序?qū)崿F(xiàn)
</>復(fù)制代碼
public class SortMain {
private static KySort sorter;
private int[] a;//定義一個(gè)數(shù)組
private SortMain(int... values) { //構(gòu)造函數(shù)
a = values;
}
public static void main(String[] args) {
setSorter(new QuickSort());
SortMain arr;
arr = new SortMain(5, 4, 3, 2, 1, 0);
arr.display();
arr.kySort();
arr.display();
System.out.println("--------");
arr = new SortMain(54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28);
arr.display();
arr.kySort();
arr.display();
System.out.println("--------");
arr = new SortMain(32, 103, 24, 88, 95, 70, 97, 15, 102, 6, 79, 46, 51, 37, 93, 108, 9, 58, 53, 58, 79, 36, 58, 91, 78, 58, 61, 81); //初始化數(shù)組
arr.display();
arr.kySort();
arr.display();
}
private static void setSorter(KySort sorter) {
SortMain.sorter = sorter;
}
private void display() {
for (int i : a) { //遍歷數(shù)組中每一個(gè)元素
System.out.print(i + " "); //展示
}
System.out.println();
}
private void kySort() {
sorter.kySort(a, a.length);
}
}
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/68246.html
摘要:算法描述冒泡排序是一種簡(jiǎn)單的排序算法。算法描述和實(shí)現(xiàn)一般來說,插入排序都采用在數(shù)組上實(shí)現(xiàn)。平均情況希爾排序年發(fā)明第一個(gè)突破的排序算法是簡(jiǎn)單插入排序的改進(jìn)版它與插入排序的不同之處在于,它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個(gè)庫(kù),讀者可以Clone下來本地嘗試。此博文配合源碼體驗(yàn)更棒哦~~~ 個(gè)人博客:Damonare的個(gè)人博客 原文地址:...
摘要:此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要:數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)經(jīng)過前面文章的鋪墊,我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí),接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規(guī)模數(shù)據(jù)轉(zhuǎn)換為插入排序會(huì)有效果提升。它只能對(duì)整數(shù)進(jìn)行排序。 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)經(jīng)過前面文章的鋪墊,我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí),接下來就可以進(jìn)入算法的鞏固階段了。首先我們來看常見的排序算法。 冒泡排序 原理...
閱讀 2968·2021-11-17 09:33
閱讀 3128·2021-11-16 11:52
閱讀 492·2021-09-26 09:55
閱讀 2989·2019-08-30 15:52
閱讀 1325·2019-08-30 15:44
閱讀 1272·2019-08-30 13:59
閱讀 807·2019-08-30 13:08
閱讀 1168·2019-08-30 10:50