排序

• 排序規則
• 一、冒泡排序
• • 1.BubbleSort-代碼呈現
  • 2.BubbleSort-代碼優化
• 二、選擇排序
• • SelectionSort-代碼呈現
• 三、冒泡與選擇排序比較
• 四、插入排序
• • InsertSort-代碼呈現
• 四、插入排序與選擇排序的比較
• 五、希爾排序
• 總結

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：國際域名空間、虛擬空間、營銷軟件、網站建設、漠河網站維護、網站推廣。

---

排序規則

??排序就是將一組對象按照某種邏輯順序重新排列的過程。主要關注的排序算法是對數組元素而言的排序算法。排序的目的是使數組正序索引的元素也是正序或逆序的。

---

一、冒泡排序

??相鄰兩個元素進行比較，前一個小于后一個位置不動，前一個大于后一個，位置互換。

1.BubbleSort-代碼呈現

public class BubbleSort {public static void main(String[] args) {int[] a = new int[]{5, 9, 7, 4, 1, 3, 2, 8};
        bubble(a);
    }

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

            System.out.println("第" + j + "輪冒泡" + Arrays.toString(a));
        }

    }

    public static void swap(int[] a, int i, int j) {int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

代碼運行效果：

2.BubbleSort-代碼優化

??由上述的方法，可以知道不是程序最優的方式，有以下兩種方法可以改進程序的運行效率：

??①比較次數是可以逐級遞減的，利用外層j不斷增長，減少內層循環的比較次數

public static void bubble(int[] a){for (int j = 0; j< a.length-1; j++) {for (int i = 0; i< a.length-1-j; i++) {System.out.println("比較次數"+i);
                if (a[i] >a[i + 1]) {swap(a, i, i + 1);
                }
            }
            System.out.println("第"+j+"輪冒泡"+Arrays.toString(a));
        }
    }

??②減少不必要的冒泡次數，判斷什么時候數組有序(判斷是否發生交換)

public static void bubble(int[] a){boolean swapped=false;//是否發生交換
        for (int j = 0; j< a.length-1; j++) {for (int i = 0; i< a.length-1-j; i++) {System.out.println("比較次數"+i);
                if (a[i] >a[i + 1]) {swap(a, i, i + 1);
                    swapped=true;
                }
            }
            System.out.println("第"+j+"輪冒泡"+Arrays.toString(a));
            if (!swapped){break;
            }
        }
    }

二、選擇排序

??選擇出最小的元素，把最小的元素放在最前面，使數組有序。

SelectionSort-代碼呈現

public class SelectionSort {public static void main(String[] args) {int[] a={5,3,7,2,1,9,8,4};
        selection(a);
    }
    public static void selection(int[] a){for (int i = 0; i< a.length-1; i++) {//i 代表每輪選擇最小元素要交換到的目標索引
            int s=i;//代表最小元素的索引
            for (int j = s+1; j< a.length; j++) {if(a[s]>a[j]){s=j;
                }
            }
            if(s!=i){swap(a,s,i);
            }
            System.out.println(Arrays.toString(a));
        }
    }
    public static void swap(int[] a,int i,int j){int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

以上代碼已優化：為減少交換次數，每一輪可以先找最小的索引，在每輪最后再交換元素。
代碼運行結果：

三、冒泡與選擇排序比較

??①二者平均時間復雜度都是O(n^2)
??②選擇排序一般要快于冒泡，因為其交換次數少
??③但如果集合有序度高，冒泡優于選擇
??④冒泡屬于穩定排序算法，而選擇屬于不穩定排序

四、插入排序

??分成未排序和排序區域，從未排序中取一個元素，相互比較，將值插入到空出的排序區域。

InsertSort-代碼呈現

public class InsertSort {public static void main(String[] args) {int[] a={9,3,7,2,5,8,1,4};
        insert(a);
    }
    public static void insert(int[] a){//i 代表待插入元素的索引
        for (int i = 0; i< a.length; i++) {int t=a[i];//代表待插入的元素值
            int j=i-1;//代表已排序區域的元素索引
            while (j>=0){if(ta[j+1]=a[j];
                }else {break;//退出循環，減少比較次數
                }
                j--;
            }
            a[j+1]=t;
            System.out.println(Arrays.toString(a));
        }
    }
}

優化方式：待插入元素進行比較，遇到比自己小的元素，就代表找到插入位置，無需進行后續比較。
代碼運行結果：

四、插入排序與選擇排序的比較

??①二者平均時間復雜度都是O(n^2)
??②大部分情況下，插入都略優于選擇
??③有序集合插入的時間復雜度為O(n)
??④插入屬于穩定排序算法，而選擇屬于不穩定排序。

五、希爾排序

??把間隙相同的元素劃為一組，同組中使用插入排序，直到間隙為1時，整體排序完成。

總結

??冒泡排序：(升序為例)依次比較數組中相鄰兩個元素的大小，若a[i]>a[i+1]，則交換兩個元素，兩兩都比較一遍稱為一輪冒泡，結果是讓大的元素排至最后；重復以上的步驟，直到整個數組有序。
??選擇排序：(升序為例)將數組分為兩個子集，排序的和未排序的，每一輪從未排序的子集中選出最小的元素，放入排序子集中；重復以上步驟，直到整個數組有序。
??插入排序：(升序為例)將數組分為兩個區域，排序區域和未排序區域，每一輪從未排序區域中取出第一個元素，插入到排序區域(需保證順序)；重復以上步驟，直到整個數組有序。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

本文標題：(冒泡、選擇、插入和希爾)排序的內容-創新互聯
本文鏈接：http://vcdvsql.cn/article12/csigdc.html

成都網站建設公司_創新互聯，為您提供云服務器、響應式網站、全網營銷推廣、手機網站建設、商城網站、小程序開發

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯