Home Java javaTutorial Java implementation of sorting algorithms: insertion sort, selection sort, bubble sort

Java implementation of sorting algorithms: insertion sort, selection sort, bubble sort

Nov 10, 2016 am 10:54 AM

package sort;
  
/**
 * @author lei 2011-8-17
 */
public class Sort {
  
    /**
     * 选择排序: 
     * 首先在数组中查找最小值, 如果该值不在第一个位置, 那么将其和处在第一个位置的元素交换,然后从第二个位置重复
     * 此过程,将剩下元素中最小值交换到第二个位置 。当到最后一位 时,数组排序结束 
     * 复杂度为:O(n^2)
     * 
     * @param array
     */
    static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min_idx = i;
  
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min_idx]) {
                    min_idx = j;
                }
            }
  
            if (min_idx != i) {
                swap(array, min_idx, i);
            }
  
        }
    }
  
    /**
     * 冒泡排序法: 
     * 是运用数据值比较后,依判断规则对数据位置进行交换,以达到排序的目的 
     * 复杂度都是O(n^2)
     * 
     * @param array
     */
    public static void bubbleSort(int[] array) {// 冒泡排序算法
        int out, in;
        // 外循环记录冒泡次数
        for (out = array.length - 1; out >= 1; out--) {
            boolean flag = false;
            // 进行冒泡
            for (in = 0; in < out; in++) {
                // 交换数据
                if (array[in] > array[in + 1]) {
                    swap(array, in, in + 1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
  
        }
    }
  
    /**
     * 插入排序 
     * 是对于欲排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的。 
     * 插入排序的最差和平均情况的性能是O(n^2)
     * 
     * @param array
     */
    public static void insertSort(int[] array) {// 插入排序算法
        int in, out;
        for (out = 1; out < array.length; out++) {// 外循环是给每个数据循环
            int temp = array[out]; // 先取出来保存到临时变量里
            in = out; // in是记录插入数据之前的每个数据下标
            // while内循环是找插入数据的位置,并且把该位置之后的数据(包括该位置)
            // 依次往后顺移。
            while (in > 0 && array[in - 1] >= temp) {
                array[in] = array[in - 1]; // 往后顺移
                --in; // 继续往前搜索
            }
            array[in] = temp; // 该数据要插入的位置
        }
    }
  
    /**
     * 交换数组数据
     * 
     * @param array
     * @param min_idx
     * @param i
     */
    private static void swap(int[] array, int min_idx, int i) {
        int temp = array[min_idx];
        array[min_idx] = array[i];
        array[i] = temp;
    }
  
    public static void main(String[] args) {
  
        int[] array = new int[] { 1, 2, 6, 5, 7, 9, 0, 121, 4545 };
        bubbleSort(array);
        for (int i : array) {
            System.out.println(i);
        }
  
    }
  
}
Copy after login

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Roblox: Bubble Gum Simulator Infinity - How To Get And Use Royal Keys
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Fusion System, Explained
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers Of The Witch Tree - How To Unlock The Grappling Hook
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1667
14
PHP Tutorial
1273
29
C# Tutorial
1255
24
Is the company's security software causing the application to fail to run? How to troubleshoot and solve it? Is the company's security software causing the application to fail to run? How to troubleshoot and solve it? Apr 19, 2025 pm 04:51 PM

Troubleshooting and solutions to the company's security software that causes some applications to not function properly. Many companies will deploy security software in order to ensure internal network security. ...

How do I convert names to numbers to implement sorting and maintain consistency in groups? How do I convert names to numbers to implement sorting and maintain consistency in groups? Apr 19, 2025 pm 11:30 PM

Solutions to convert names to numbers to implement sorting In many application scenarios, users may need to sort in groups, especially in one...

How to simplify field mapping issues in system docking using MapStruct? How to simplify field mapping issues in system docking using MapStruct? Apr 19, 2025 pm 06:21 PM

Field mapping processing in system docking often encounters a difficult problem when performing system docking: how to effectively map the interface fields of system A...

How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log? How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log? Apr 19, 2025 pm 11:45 PM

Start Spring using IntelliJIDEAUltimate version...

How to elegantly obtain entity class variable names to build database query conditions? How to elegantly obtain entity class variable names to build database query conditions? Apr 19, 2025 pm 11:42 PM

When using MyBatis-Plus or other ORM frameworks for database operations, it is often necessary to construct query conditions based on the attribute name of the entity class. If you manually every time...

How to safely convert Java objects to arrays? How to safely convert Java objects to arrays? Apr 19, 2025 pm 11:33 PM

Conversion of Java Objects and Arrays: In-depth discussion of the risks and correct methods of cast type conversion Many Java beginners will encounter the conversion of an object into an array...

How to use the Redis cache solution to efficiently realize the requirements of product ranking list? How to use the Redis cache solution to efficiently realize the requirements of product ranking list? Apr 19, 2025 pm 11:36 PM

How does the Redis caching solution realize the requirements of product ranking list? During the development process, we often need to deal with the requirements of rankings, such as displaying a...

E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products? E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products? Apr 19, 2025 pm 11:27 PM

Detailed explanation of the design of SKU and SPU tables on e-commerce platforms This article will discuss the database design issues of SKU and SPU in e-commerce platforms, especially how to deal with user-defined sales...

See all articles