Java データ構造の 7 つのソート方法の使用方法-＆＃＆チュートリアル-php.cn

##1. 挿入ソート

1. 直接挿入ソート

i 番目 (i>=1) 要素を挿入する場合、先ほどのarray[0]、array[1]、...、array[i-1]はソートされていますので、今回はarray[i]とarray[i-1]、array[i-2]、を使用します。 .. 比較して挿入位置を見つけ、array[i]を挿入し、元の位置の要素を後方に移動します。

データの順序が近いほど、sort を直接挿入するのにかかる時間が短くなります。

時間計算量: O(N^2)

空間計算量 O(1) は安定したアルゴリズムです

直接挿入ソート:

Java データ構造の 7 つのソート方法の使用方法

    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for(;j>=0;--j){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

ログイン後にコピー

2. ヒルソート

ヒルソート方法の基本的な考え方は、まず整数ギャップを選択し、ソートするファイル内のすべてのレコードをギャップグループに分割し、すべてのレコードをギャップグループに分割します。ギャップの距離を持つ数値は同じグループに属し、各グループの数値が直接挿入されて並べ替えられます。次に、gap=gap/2 を取得し、上記のグループ化と並べ替えの作業を繰り返します。ギャップ=1 の場合、すべての数値はグループ内で直接並べ替えられます。

ヒルソートは、直接挿入ソートを最適化したものです。
目的は、配列を順序に近づけることであるため、ギャップ > 1 の場合は事前ソートが実行されます。挿入ソートは、ギャップが 1 の場合、ほぼ順序付けされた配列を迅速にソートできます。
ヒルソートの時間計算量は計算が困難です。これは、ギャップ値を取得する方法が多数あり、計算が困難であるためです。

public static void shellSort(int[] array){
        int size=array.length;
        //这里定义gap的初始值为数组长度的一半
        int gap=size/2;
        while(gap>0){
            //间隔为gap的直接插入排序
            for (int i = gap; i < size; i++) {
                int tmp=array[i];
                int j=i-gap;
                for(;j>=0;j-=gap){
                    if(array[j]>tmp){
                        array[j+gap]=array[j];
                    }else{
                        break;
                    }
                }
                array[j+gap]=tmp;
            }
            gap/=2;
        }
    }

ログイン後にコピー

2. 選択範囲の並べ替え

#1. 選択範囲の並べ替え

#このセットの最初の要素でない場合は、要素セット内の最小のデータ要素を選択します要素を 1 つ追加し、それをこの要素セットの最初の要素と交換します。
#残りのセットでは、セットに 1 つの要素が残るまで上記の手順を繰り返します
時間計算量: O(N^2)

選択の並べ替え:

    //交换
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    //选择排序
    public static void chooseSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;//记录最小值的下标
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]) {
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }

ログイン後にコピー

2. ヒープソート

ヒープソートに関する 2 つのアイデア (例として昇順): Java データ構造の 7 つのソート方法の使用方法

小さなルートヒープを作成します。 order ヒープの先頭要素を取り出し、ヒープが空になるまで配列に入れます。

大きなルートヒープを作成し、ヒープの末尾要素の位置キーを定義し、交換します。キーがヒープの先頭に到達するまで、ヒープの先頭の要素とキーの位置にある要素 (key --) が毎回実行されます。このとき、ヒープ内の要素の順次走査は昇順になります (次のように)以下)
時間計算量: O(N^2)

空間計算量: O(N)、不安定

ヒープソート:

    //向下调整
    public static void shiftDown(int[] array,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len){
                if(array[child+1]>array[child]){
                    child++;
                }
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
 
        }
    }
    //创建大根堆
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        //创建大根堆
        createHeap(array);
        //排序
        for (int i = array.length-1; i >0; i--) {
            swap(array,0,i);
            shiftDown(array,0,i);
        }
    }

ログイン後にコピー

3. Exchange sort

1 、バブルソート Java データ構造の 7 つのソート方法の使用方法

2 レベルのループ、最初のレベルのループは、交換の回数を示します。ソートされ、第 2 レベルのループは各パスで行われる比較の数を示します。ここでのバブルソートは最適化されており、各パスで比較するときに、データ交換の数を記録するカウンターを定義できます。は交換ではありません。これは、データがすでに整っていて、それ以上の並べ替えが必要ないことを意味します。

時間計算量: O(N^2)

空間計算量は O(1) で、これは安定したソートです

バブルソート:

   public static void bubbleSort(int[] array){
        for(int i=0;i<array.length-1;++i){
            int count=0;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    count++;
                }
            }
            if(count==0){
                break;
            }
        }
    }

ログイン後にコピー

2. クイックソート

並べ替える要素のシーケンス内の任意の要素を基本値として取得し、並べ替えコードに従って並べ替えるセットを 2 つのサブシーケンスに分割します。左側のサブシーケンスのすべての要素が基本値より小さく、右側のサブシーケンスのすべての要素が基本値より大きい場合、すべての要素が対応する位置に配置されるまで、このプロセスが左右のサブシーケンスに対して繰り返されます。 Java データ構造の 7 つのソート方法の使用方法

時間計算量: 最良の O (N*Logn): 毎回ソートされるシーケンスを均等に分割することを試みることができます。順序付き

空間計算量: 最良の O(logn)、最悪の O (N)。不安定なソート

(1) 穴掘り法

データが整然としている場合、クイックソートは左右の部分木のない二分木と同等となり、このとき空間複雑度はO(N)、大量のデータをソートすると、スタックオーバーフローが発生する可能性があります。

public static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int l=left;
        int r=right;
        int tmp=array[l];
        while(l<r){
            while(array[r]>=tmp&&l<r){
            //等号不能省略，如果省略，当序列中存在相同的值时，程序会死循环
                r--;
            }
            array[l]=array[r];
            while(array[l]<=tmp&&l<r){
                l++;
            }
            array[r]=array[l];
        }
        array[l]=tmp;
        quickSort(array,0,l-1);
        quickSort(array,l+1,right);
    }

ログイン後にコピー

(2) クイックソートの最適化

3つの数値の中間の方法でキーを選択します

キー値の選択については、ソートする順序が次の場合、最初または最後のキーをキーとして選択すると、分割の左側または右側が空になる可能性があり、この場合、クイックソートのスペースの複雑さが比較的大きくなり、スタックオーバーフローが発生しやすくなります。そうすれば、この状況を解消するには、3 ナンバー法を使用できます。シーケンス内の最初、最後、中間の要素の中央の値がキー値として使用されます。

 //key值的优化，只在快速排序中使用，则可以为private
    private int threeMid(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]>array[right]){
            if(array[mid]>array[left]){
                return left;
            }
            return array[mid]<array[right]?right:mid;
        }else{
            if(array[mid]<array[left]){
                return left;
            }
            return array[mid]>array[right]?right:mid;
        }
    }

ログイン後にコピー

小さな部分範囲を再帰する場合は、挿入ソートの使用を検討できます

随着我们递归的进行，区间会变的越来越小，我们可以在区间小到一个值的时候，对其进行插入排序，这样代码的效率会提高很多。

（3）快速排序的非递归实现

 //找到一次划分的下标
    public static int patition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //快速排序的非递归
    public static void quickSort2(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int r=stack.pop();
            int l=stack.pop();
            int p=patition(array,l,r);
            if(p-1>l){
                stack.push(l);
                stack.push(p-1);
            }
            if(p+1<r){
                stack.push(p+1);
                stack.push(r);
            }
        }
    }

ログイン後にコピー

四、归并排序

归并排序（MERGE-SORT）：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。实现序列的完全有序，需要将已经有序的子序列合并，即先让每个子序列有序，然后再将相邻的子序列段有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度：O(n*logN)（无论有序还是无序）

空间复杂度：O（N）。是稳定的排序。

Java データ構造の 7 つのソート方法の使用方法

    //归并排序：递归
    public static void mergeSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        //递归分割
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        //合并
        merge(array,left,right，mid);
    }
    //非递归
    public static void mergeSort1(int[] array){
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=left+2*gap-1;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap=gap*2;
        }
    } 
    //合并：合并两个有序数组
    public static void merge(int[] array,int left,int right，int mid){
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        for (int i = left; i <= right; i++) {
            array[i]=tmp[i-left];
        }
    }

ログイン後にコピー

五、排序算法的分析

排序方法	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(n)	O(n^2)	O(1）	不稳定
直接排序	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlog(2)n)	O(nlog(2)n)	O(1)	不稳定
冒泡排序	O(n)	O(n^2)	O(1)	稳定
快速排序	O(nlog(2)n)	O(n^2)	O(nlog(2)n)	不稳定
归并排序	O(nlog(2)n)	O(nlog(2)n)	O(n)	稳定

以上がJava データ構造の 7 つのソート方法の使用方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。