算法排序
時間復(fù)雜度和空間復(fù)雜度
image.png
選冒插n方
快歸堆希
桶計基
- 選擇排序：第i輪選擇確定第i小的數(shù)怖亭。（正，用指針）
- 冒泡排序：第i輪冒出第i大的數(shù)摧茴。（倒，兩兩交換）
- 選擇排序 ：1.從0～i-1中插入i埂陆，兩兩交換苛白。2. 從0～i-1中插入i，大的數(shù)后移焚虱。
- 希爾排序：選擇排序1的改進(jìn)购裙，進(jìn)行分組（gap->0 gap = (gap-1)/3 )
- 合并排序：二叉樹的深度排序，對數(shù)組進(jìn)行分l鹃栽、m缓窜、r，最后對l～r進(jìn)行排序
- 快速排序：每一次確定第一個元素（基準(zhǔn)）的位置q谍咆，并且實現(xiàn)了在這個元素之前的都小于它，之后的都大于它私股。使用雙指針摹察。
- 計數(shù)排序：有一個累加桶（元素作為下標(biāo)），因此每一個元素的位置為count[attr[i]]--,進(jìn)行遍歷
- 基數(shù)排序：每一個關(guān)鍵字排序使用計數(shù)排序倡鲸，累加桶和關(guān)鍵字排序
- 堆排序：對于最大堆排序：第一個元素和最后一個元素交換供嚎，交換之后要對剩余堆從0整理；構(gòu)建：從最后一個父節(jié)點開始構(gòu)建穩(wěn)定堆峭状。
1.選擇排序
public static void main(String[] args) {
int[] attr = {2,1,5,7,9,0,3,4,8};
sort1(attr);
System.out.println(Arrays.toString(attr));
}
/**
* 選擇排序
* 功能：每一輪的枚舉i克滴，都可以確定第i小的數(shù)
* @param attr 需要排序的數(shù)組
*
*/
static void sort1(int[] attr){
for (int i = 0; i < attr.length; i++){
int minPivot = i;
for (int j = i+1; j < attr.length;j++){
minPivot = attr[minPivot] < attr[j] ? minPivot:j;
}
// 交換
swap(attr,i,minPivot);
}
}
static void swap(int[]attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
2、冒泡排序
/**
* 冒泡排序
* 每一輪的枚舉i优床，通過兩兩比較找到第i大的數(shù)
* @param attr
*/
static void sort2(int[] attr){
for (int i = attr.length-1; i > 0 ; i--) {
for (int j = 0; j < i; j++) {
if (attr[j] > attr[j+1]) swap(attr,j,j+1);
}
}
}
static void swap(int[]attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
3劝赔、插入排序
/**
* 插入排序
* 每一輪的枚舉i，往前面的i-1胆敞，中放入第i個元素
* 1.i和i-1兩兩比較着帽，之后交換
* 2.i和i-1兩兩比較杂伟，借助變量記錄attr[i],然后其余元素后移,需要注意的是attr[j] > temp放在判斷條件，
* 這樣j就不會減到0才退出仍翰，也不便于確定temp擺放的位置j
* @param attr
*/
static void sort3(int[] attr){
/* for (int i = 1; i < attr.length; i++) {
for (int j = i; j > 0; j--) {
if (attr[j] < attr[j-1]) swap(attr,j,j-1);
}
}*/
for (int i = 1; i < attr.length; i++) {
int temp = attr[i];
int j = i;
for (j = i-1; j >= 0 && attr[j] > temp ; j--) {
attr[j+1] = attr[j];
}
attr[j+1] = temp;
}
}
static void swap(int[]attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
4.希爾排序
/**
* 希爾排序
* 是對選擇排序的改進(jìn)赫粥，使用gap控制分組的間隔，可以是attr.length/2 ----- 1,排到組數(shù)為1時予借，排序結(jié)束
* 但是效率更高的是 h = h*3 + 1
* i 用來控制插入的第i個數(shù)越平，j用來控制要比較的前面的數(shù)，(i - gap)
* @param attr
*/
static void sort4(int[] attr){
int h = 1;
while (h < attr.length){
h = h*3+1;
}
int gap = h; // attr.length/2 右移一位 int gap = attr.length >> 1; gap > 0; gap /=2
for (gap = h; gap > 0; gap = (gap-1)/3){
for (int i = gap; i < attr.length; i++) {
for (int j = i; j >= gap; j = j-gap) {
if (attr[j] < attr[j-gap]) swap(attr,j,j-gap);
}
}
}
}
static void swap(int[]attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
5.合并排序
/**
* 合并排序
* 使用遞歸的策略灵迫，每次將數(shù)組分半秦叛，l m r
* 之后使用merge對(l, m) (m+1,r) 這兩段數(shù)組排序(l, r)
* @param attr 待排序的數(shù)組
* @param left 數(shù)組的第一個元素下標(biāo)
* @param right 數(shù)組的最后一個元素下標(biāo)
*/
static void mergeSort5(int[] attr, int left, int right){
if (left < right){ // {2,1,5,7,9,0,3,4,8};
int mid = left+(right-left)/2;
mergeSort5(attr,left,mid);
mergeSort5(attr,mid+1,right);
merge(attr, left, mid, right);
}
}
private static void merge(int[] attr, int left, int mid, int right) {
int[] tmp = new int[right-left+1]; // l = 0 mid = 0 right = 1
int i = left;
int j = mid+1;
int k = 0;
while (i <= mid && j <= right){
tmp[k++] = attr[i] < attr[j] ? attr[i++]:attr[j++];
}
while (i <= mid) tmp[k++] = attr[i++];
while (j <= right) tmp[k++] = attr[j++];
for (int l = 0; l < tmp.length; l++) {
attr[left+l] = tmp[l];
}
}
6.快速排序
/**
* 快速排序
* 以第一個元素作為基準(zhǔn)，通過左右指針的移動i,j,當(dāng)i和j相遇時龟再，代表此時j指向了第一個元素該放的位置书闸。
* 使用了i，j指針利凑，以及一個變量的基準(zhǔn)
* @param attr 待排序數(shù)組
* @param left 數(shù)組的第一個元素下標(biāo)
* @param right 數(shù)組的最后一個元素下標(biāo)
*/
static void quickSort6(int[] attr, int left, int right){
if (left < right){
int q = partition(attr, left, right);
quickSort6(attr,left,q-1);
quickSort6(attr,q+1, right);
}
}
private static int partition(int[] attr, int left, int right) {
Random random = new Random();
int x = random.nextInt(right+1-left)+left;
swap(attr,x,left);
int pivot = attr[left];
int i = left;
int j = right+1;
while (true){
while (i < right && attr[++i] <= pivot);
while (j > left && attr[--j] > pivot);
if (i >= j) break;
swap(attr,i,j);
}
swap(attr,j,left);
return j;
}
static void swap(int[]attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
7.計數(shù)排序
/**
* 計數(shù)排序
* count 存儲這個數(shù)出現(xiàn)的次數(shù)浆劲，并且這個數(shù)是index下標(biāo)
* count作為累加的桶，attr[i]對應(yīng)的位置為：--count[attr[i]]
* @param attr 待排序數(shù)組
* @return 排好序的數(shù)組
*/
static int[] countSort(int[] attr){
int[] res = new int[attr.length];
int[] count = new int[10];
for (int i = 0; i < res.length; i++) {
count[attr[i]]++;
}
for (int i = 1; i < count.length; i++) {
count[i] = count[i]+count[i-1];
}
for (int i = attr.length-1; i >= 0; i--) {
res[--count[attr[i]]] = attr[i];
}
return res;
}
8.基數(shù)排序
public static void main(String[] args) {
int[] attrs = {237,456,123,456,789,987,123,456,789};
System.out.println(Arrays.toString(radixSort(attrs)));
}
/**
* 基數(shù)排序
* 多關(guān)鍵字排序：低位優(yōu)先
* 先對個位排序哀澈，再對十位排序牌借，最后對百位排序
* 對每一個關(guān)鍵字的排序，使用了計數(shù)排序
* @param attr 待排序數(shù)組
* @return 返回排好序的數(shù)組
*/
static int[] radixSort(int[] attr){
int[] res = new int[attr.length];
int[] count = new int[10];
for (int i = 0; i < 3; i++) {
int division = (int)Math.pow(10,i);
for (int j = 0; j < attr.length; j++) {
int num = attr[j]/division%10;
count[num]++;
}
for (int j = 1; j < count.length; j++) {
count[j] = count[j]+count[j-1];
}
for (int j = attr.length-1; j >= 0; j--) {
int num = attr[j]/division%10;
res[--count[num]] = attr[j];
}
System.arraycopy(res,0,attr,0,attr.length);
Arrays.fill(count,0);
}
return res;
}
- 堆排序
public static void main(String[] args) {
int[] attr = {2,5,7,3,1,0,8,9};
heapSort(attr,attr.length);
System.out.println(Arrays.toString(attr));
}
/**
* 堆排序
* 堆的特點：完全二叉樹（從下往上割按，從左往右） 每一棵子樹都滿足parent > child
* 堆的構(gòu)建 heapify膨报，從h-1層，最后一個父節(jié)點适荣，也就是最后一個節(jié)點的父節(jié)點parent = (n-1)/2,往上heapify一直到第1層现柠。
* 堆的排序：拿出堆頂元素，和堆的最后一元素交換弛矛，砍斷最后一個元素够吩，然后重新構(gòu)建堆。
* 可以用數(shù)組來表示完全二叉樹
* int[] attr = {10,5,8,3,4,....}
* i = 3
* parent = (i-1)/2
* c1 = 2*i + 1
* c2 = 2*i + 2
* @param attr
*/
static void heapSort(int[] attr,int n){
buildHeap(attr,n);
System.out.println(Arrays.toString(attr)+"--------");
int i;
for (i = n-1;i >= 0;i--){
swap(attr,i,0);
heapify(attr,i,0);
}
}
static void buildHeap(int[] attr,int n){
int lastNode = n-1;
int parent = (lastNode-1)/2;
for (int i = parent; i >= 0 ; i--) {
heapify(attr,n,i);
}
}
static void heapify(int[] attr,int n,int i){
// 遞歸出口
if (i > n) return;;
// 對第i個節(jié)點排序丈氓，它下面的元素是穩(wěn)定的
int c1 = i*2+1;
int c2 = i*2+2;
int max = i;
if (c1 < n && attr[c1] > attr[max]){
max = c1;
}
if (c2 < n && attr[c2] > attr[max]){
max = c2;
}
if (max != i){
swap(attr,i,max);
heapify(attr,n,max);
}
}
static void swap(int[] attr, int i, int j){
int temp = attr[i];
attr[i] = attr[j];
attr[j] = temp;
}
