Jimmy小站

小明也有大梦想 — 蒋明/铭
当前位置:网站首页 / 数据结构算法 / 正文

冒泡排序,选择排序,插入排序,希尔排序

2016-03-23 / 数据结构算法 / 2569 次围观 / 0 次吐槽

几种简单的排序算法,记录在博客中,主要学习下其中的思想。


冒泡排序

  1.   (遍历下标 0 -> i) 将相邻两个元素比较

  2. 将较大的放到后面,直到下标为 i ,即表明下标 i 及以后的元素排序完成

  3. 再次(遍历下标 0 -> i-1)

  4. 再次(遍历下标 0 -> i-2)

  5. ......

  6. 直到剩下最后一个元素

package net.jimmyme;

import java.util.Arrays;

public class BubbleSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        bubbleSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void bubbleSort(){
        
        for (int i = 0; i < source.length; i++) {
            for (int j = 0; j < source.length-1-i; j++) {
                if (source[j] > source[j+1]) {
                    
                    int temp = source[j+1];
                    source[j+1] = source[j];
                    source[j] = temp;
                }
            }
        }
    }

}

选择排序

  1. 遍历下标 0 -> n  选出最小的元素(下标为 i)

  2. 交换 下标为 0 与 i 的元素

  3. 再次(遍历下标 1 -> n) 选出最小的元素(下标为 i)

  4. 交换

  5. ......

  6. 直到剩下最后一个元素

package net.jimmyme;

import java.util.Arrays;

public class SelectSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        selectSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void selectSort(){
        
        for (int i = 0; i < source.length; i++) {
            int min = i;
            for (int j = i+1; j < source.length; j++) {
                // find the index of min value 
                if (source[j] < source[min]) {
                    
                    min = j;
                }
            }
            //swap
            int temp = source[i];
            source[i] = source[min];
            source[min] = temp;
            
        }
    }

}

插入排序

  1. 第0位元素保持不动,从第一位开始,将选取的元素与已经有序的序列对比

  2. 找到前面小于等于 该元素  后面大于等于该元素的位置

  3. 将该元素 插入两者之间

  4. 直到所有元素都插入

package net.jimmyme;

import java.util.Arrays;

public class InsertSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        insertSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void insertSort(){
        
        for (int i = 1; i < source.length; i++) {
            
            int temp = source[i]; //选中第i个元素
            int j = i-1; // 从第i-1元素开始 往前找 只要比temp大就往后移
            
            while (j >= 0 && source[j] > temp) {
                source[j+1] = source[j];
                j--;
            }
            // 直到找到前面一个比自己小,后一个就是该元素的位置
            source[j+1] = temp;
        }
    }
}

希尔排序

    希尔排序就是插入排序的优化版本,将步长定为 d ,分成 d 个组,每个组进行插入排序,经过一轮之后 逐步缩短步长 d 。直到步长变为1(标准插入排序)

package net.jimmyme;

import java.util.Arrays;

public class ShellSort {

    public static int source[] = {101,8,9,13,45,17,26,99,78,11,46};
    public static void main(String[] args) {
        
        shellSort();
        System.out.println(Arrays.toString(source));
    }
    
    public static void shellSort(){
        int d = source.length/2;
        
        while (d > 0) {
            // 相当于步长为d的插入排序法,且步长逐渐缩小,当步长为1时 就是标准的插入排序
            for (int i = d; i < source.length; i++) {
                int j = i-d;
                int temp = source[i];
                while (j >= 0 && source[j] > temp) {
                    source[j+d] = source[j];
                    j -= d;
                }
                
                source[j+d] = temp;
            }
            d /= 2;
        }
        
    }
}


推荐您阅读更多有关于“排序算法Java,”的文章

[一个Java程序猿的转型之路,读研深造,专注机器学习推荐算法]
本站所有文章如无特别注明均为原创。作者:吉米酱 ,复制或转载请以超链接形式注明转自 Jimmy小站
原文地址《冒泡排序,选择排序,插入排序,希尔排序
额 本文暂时没人评论 来添加一个吧

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996