バブル、選択、挿入、二分挿入、ヒル、スタック、集計および基数ソートアルゴリズムの小結
各種アルゴリズムは直接コードをアップロードし、主にソートアルゴリズムの安定性の概念を提出したい.
通俗的には、ソート前の2つの等しい数は、シーケンスの前後位置順序とソート後の2つの前後位置順序が同じであることが保証される.簡単な形式化では、Ai=Aj、Aiが元の位置の前にある場合、ソート後のAiはAjの位置の前にある必要があります.
一般的な状況:
選択ソート、高速ソート、ヒルソート、スタックソートは安定したソートアルゴリズムではなく、バブルソート、挿入ソート、集計ソート、および基数ソートは安定したソートアルゴリズムである.
ソートアルゴリズムが安定であるかどうかは具体的なアルゴリズムによって決定され、不安定なアルゴリズムはある条件下で安定なアルゴリズムになり、安定したアルゴリズムはある条件下で不安定なアルゴリズムになることができる.
泡のソート:
ソートを選択:
直接挿入ソート:
二分挿入ソート:
ヒルソート:
ヒープのソート:
集計ソート:
基数ソート:
抽象クラス:
gitソースコード
通俗的には、ソート前の2つの等しい数は、シーケンスの前後位置順序とソート後の2つの前後位置順序が同じであることが保証される.簡単な形式化では、Ai=Aj、Aiが元の位置の前にある場合、ソート後のAiはAjの位置の前にある必要があります.
一般的な状況:
選択ソート、高速ソート、ヒルソート、スタックソートは安定したソートアルゴリズムではなく、バブルソート、挿入ソート、集計ソート、および基数ソートは安定したソートアルゴリズムである.
ソートアルゴリズムが安定であるかどうかは具体的なアルゴリズムによって決定され、不安定なアルゴリズムはある条件下で安定なアルゴリズムになり、安定したアルゴリズムはある条件下で不安定なアルゴリズムになることができる.
泡のソート:
/**
*
*
* :
。 ， 。
， 。 ， 。
， 。
， 。
* O(n^2) O(n^2) ， ， O(1) n
*
* ： ， ，
* Created by Administrator on 2017/3/12 0012.
*/
public class BubbleSort extends DataSort{
@Override
public void dataSort() {
int length = sourceArray.length;
for(int i=0;isourceArray[j+1]){
swap(sourceArray,j,j+1);
}
}
}
}
} ソートを選択:
/**
*
* ， 。 ， …… ，
* ，
* O(n^2) O(n^2) ， ， O(1) n
* Created by Administrator on 2017/3/12 0012.
*/
public class SelectSort extends DataSort {
@Override
public void dataSort() {
int length = sourceArray.length;
for(int i=0;i直接挿入ソート:
/**
*
* ， 。
* ， 1 ， 。
* ， ， ， 。
* ，
* ， 。
* ，
* O(n^2) O(n^2) ， ， O(1)
* Created by Administrator on 2017/3/12 0012.
*/
public class InsertSort extends DataSort {
@Override
public void dataSort() {
int length = sourceArray.length;
for(int i=1;i=0;j--){
if(sourceArray[j]>temp){
sourceArray[j+1] = sourceArray[j];
}else{
break;
}
}
sourceArray[j+1] = temp;
}
}
}
二分挿入ソート:
/**
*
* i ， 0～i-1 ， ， ， ， ，
* left>right， i 1 ， i 。
* 0 ， i ， i ， ， i
* O(n^2) O(n^2) ， ， O(1) ,
* Created by Administrator on 2017/3/12 0012.
*/
public class BinaryInsertSort extends DataSort {
@Override
public void dataSort() {
int length = sourceArray.length;
for (int i=0;i=left;j--){
sourceArray[j+1] = sourceArray[j];
}
//left == i
if(left != i){
sourceArray[left] = temp;
}
}
}
}
ヒルソート:
/**
* , 。
* O(nlogn) O(n^s 1=0;k-=addUp){
if(tempヒープのソート:
/**
*
* (Heapsort) （ ） ， 。
* 。 ， 。
* ， A[PARENT[i]] >= A[i]。
* ， ， ，
* O(nlogn) O(nlogn) ， ， O(1) ,n
* Created by Administrator on 2017/3/12 0012.
*/
public class HeapSort extends DataSort {
@Override
public void dataSort() {
buildLatestHeap(sourceArray);
headSort(sourceArray);
}
/**
* ，
*/
private void headSort(int[] array){
// ，
for (int i = array.length-1; i > 0 ; i--) {
swap(array,i,0);
// ， ， ， index 0
maxHeap(array,i,0);
}
}
/**
*
* @param array
*/
private void buildLatestHeap(int[] array){
if(array == null || array.length == 0){
return;
}
// ， length/2
int maxLength = array.length/2;
for(int i=maxLength;i>=0;i--){
maxHeap(array,array.length,i);
}
}
/**
*
* @param array
* @param length
* @param i
*/
private void maxHeap(int[] array,int length,int i){
int leftNode = 2*i+1;
int rightNode = 2*i +2;
int latestIndex = i;
if(leftNodearray[latestIndex]){
latestIndex = leftNode;
}
if(rightNodearray[latestIndex]){
latestIndex = rightNode;
}
// i latestIndex ， ，
if(i != latestIndex){
swap(array,i,latestIndex);
//
maxHeap(array,length,latestIndex);
}
}
}
集計ソート:
/**
*
* （MERGE-SORT） , （Divide and Conquer） 。
* ， ； ， 。 ， 。
* ： a[i] a[j] ， a[i]≤a[j]， a[i] r[k] ， i k 1；
* a[j] r[k] ， j k 1， ， ，
* r k t 。
* ， [s,t] ， ， ，
* [s,t]。
* O(nlogn) O(nlogn) ， ， O(1) ,n
* Created by Administrator on 2017/3/12 0012.
*/
public class MergeSort extends DataSort {
@Override
public void dataSort() {
mergeSort(sourceArray,0,sourceArray.length-1);
}
private void mergeSort(int[] array,int left,int right){
if(left < right){
int middle = (left+right)/2;
mergeSort(array,left,middle);
mergeSort(array,middle+1,right);
mergeData(array,left,middle,right);
}
}
/**
*
* ， ， ， left middle middle right
* @param array
* @param left
* @param middle
* @param right
*/
private void mergeData(int[] array,int left, int middle, int right){
// ，
int[] tempArray = new int[right - left + 1];
int rightStart = middle + 1;
int tempLeft = left;
int tempIndex = 0;
// ，
while(left<=middle && rightStart<=right){
if(array[left]<=array[rightStart]){
tempArray[tempIndex++] = array[left++];
}else{
tempArray[tempIndex++] = array[rightStart++];
}
}
//
while(left<=middle){
tempArray[tempIndex++] = array[left++];
}
//
while(rightStart<=right){
tempArray[tempIndex++] = array[rightStart++];
}
// tempArray array
for(int i=0;i基数ソート:
/** ( ， )
* （radix sort） “ ”（distribution sort）， “ ”（bucket sort） bin sort，
* ， ， “ ” ， ， ，
* O (nlog(r)m)， r ， m ， ， 。
* Created by Administrator on 2017/3/12 0012.
*/
public class RadixSort extends DataSort {
@Override
public void dataSort() {
int length = sourceArray.length;
// ，
int maxLength = 1;
// ，
int temp = 0;
for(int i=0;i> baseIndexList = new ArrayList<>();
for(int i=0;i<10;i++){
baseIndexList.add(new ArrayList());
}
for(int i=0;i0){
sourceArray[index++] = baseIndexList.get(k).get(0);
// ，
baseIndexList.get(k).remove(0);
}
}
}
}
} 抽象クラス:
/**
* Created by Administrator on 2017/3/12 0012.
*/
public abstract class DataSort {
/**
* ，
*/
protected int[] sourceArray = new int[]{20,12,3,5974,1,2,43,12,0,8,89,1235,235,66,897,586};
/**
* sort the data
*/
public abstract void dataSort();
/**
* i j
* @param desArray
* @param i
* @param j
*/
public void swap(int[] desArray , int i , int j){
if(desArray == null || i < 0 || j < 0 || i >= desArray.length || j >= desArray.length || i==j){
//do nothing
return;
}
desArray[i] ^= desArray[j];
desArray[j] ^= desArray[i];
desArray[i] ^= desArray[j];
}
/**
* array
* @param array
* @return
*/
public String arrayToString(int[] array){
if(array == null ){
return null;
}
if(array.length == 0){
return "";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
int length = array.length;
for (int i=0;igitソースコード