7つのソート
8244 ワード
ソートの選択
最も簡単なアルゴリズム:まず配列の最小の要素と1つの要素の交換位置を見つけて、次に次の要素の中で最小の要素と配列の2番目の要素の交換を見つけて、このように往復します.
特徴:
import java.util.*;
public class Selection
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for(int i = 0; i < arr.length;i++){
int min = i;
for(int j = i;jバブルソート
左から右へ隣接する逆順序の要素を交換し続け、1ラウンドのループの後、並べ替えられていない最大要素を右側に浮かべることができます.
1サイクルで交換が発生しない場合は、配列が秩序化されていることを示し、直接終了することができます.
import java.util.*;
public class Bubble{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public void sort(int[] arr){
int N = arr.length;
for(int i = N-1;i>=0;i--){
for(int j = 0;j arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
public static void exch(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}ソートの挿入
ソートされた配列の適切な位置に各数を挿入すると、残りの要素は1ビット右に移動する必要があります.
特徴:
import java.util.*;
public class Insertion
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for(int i = 0 ; i < arr.length;i++){
for(int j = i;j>0 && arr[j] < arr[j-1] ;j--){
exch(arr,j,j-1);
}
}
}
public static void exch(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
ヒルソート
アイデア:
import java.util.*;
public class Shell
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
int h = 1;
int N = arr.length;
while( h < N/3)
h = 3*h + 1;
while(h >=1){
for(int i = h; i=h && arr[j] < arr[j-h];j -= h){
exch(arr,j,j-h);
}
}
h = h/3;
}
}
public static void exch(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} ヒープのソート
≪ヒープ｜Heap｜oem_src≫:各ノードが2バイト以上のポイント
スタックソートは、スタックというデータ構造によって設計されたソートアルゴリズムであり、着実に選択されたソートである.
最良、最悪、平均時間複雑度はO(Nlogn)、
アイデア:
import java.util.*;
public class Heap
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
int N = arr.length - 1;
//
for(int i = (N+1)/2 ;i >= 0 ;i--){
sink(arr,i,N);
}
while(N > 0){
exch(arr,0,N--);
sink(arr,0,N);
}
}
//
public static void sink(int[] arr,int k,int N){
while(2 * k <= N){
int j = 2 * k;
if(j < N && arr[j] < arr[j+1]) // ， j
j++;
if(arr[k] < arr[j]){ // ，
exch(arr,k,j);
k = j;
}else{
break;
}
}
}
public static void exch(int[] arr,int i ,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}集計ソート
集計ソートは、配列を再帰的に2つの半分に分けてソートし、結果を集計します.
特徴:
import java.util.*;
public class Merge
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
int[] temp = new int[arr.length];
sort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr,int left,int right,int[] temp){
if(left < right){
int mid = (left + right) / 2;
sort(arr,left,mid,temp);
sort(arr,mid + 1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left , j = mid + 1;
for(int k = left;k<=right;k++){
temp[k] = arr[k]; // arr[left .. right] temp[left .. right]
}
for(int k = left;k <= right;k++){
if(i > mid)
arr[k] = temp[j++];
else if(j > right)
arr[k] = temp[i++];
else if(temp[i] < temp[j])
arr[k] = temp[i++];
else
arr[k] = temp[j++];
}
}
}クイックソート:
高速ソートは、1つの配列を2つのサブ配列に分割し、2つの部分を独立にソートする分治的ソートアルゴリズムです.
集計ソートとの違い:
特徴:
import java.util.*;
public class Quick
{
public static void main(String[] args){
int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr,int left,int right){
merge(arr,left,right);
}
public static void merge(int[] arr,int left,int right){
if(left < right){
int i = left , j = right , t = arr[i]; // （left)
while( i < j){
while(arr[j] >= t && i < j) // ， t
j--;
arr[i] = arr[j];
while(arr[i] <= t && i < j){ // ， t
i++;
}
arr[j] = arr[i];
}
// （ ）t i， i t，i t
arr[i] = t;
merge(arr,left,i-1);
merge(arr,i+1,right);
}
}
}
まとめ
安定したアルゴリズム:
速い列の基準の3種類の選択
高速配列の最適化:
最適化の理由:並べ替えられるシーケンスの長さが小さい場合や、基本的に秩序化されている場合、高速配列の効率は挿入が良いか.