常见的简单排序算法

发表于   |   分类于   |  

本文介绍几种常见的简单排序算法，包括冒泡排序，选择排序和插入排序。

冒泡排序

冒泡排序算法的思路：
算法进行n-1趟排序，每一趟排序从未排序数组的起始位置开始，通过比较和交换的方式将最大值排到未排序数组的尾部。
比较和交换的规则：

  1. 比较两个元素的值
  2. 如果左边元素的值大于右边元素的值，则交换两个元素的位置；

  3. 向右移动第一个位置，接着比较两个元素的值 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public static void bubbleSort(long[] theArray) {
    	int out = 1, in = 0;
    	long tmp;
    	for(; out < theArray.length ; out++) { //算法进行n-1趟排序
    		for(; in < theArray.length - out; in++) { 
    			if(theArray[in] > theArray[in + 1]) {
    				tmp = theArray[in];
    				theArray[in] = theArray[in + 1];
    				theArray[in + 1] = tmp;
    			}
    		}
    	}
    	
    }

选择排序

选择排序算法的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectSort(long[] theArray) {
	int out, in, max;
	long tmp;
	for(out = theArray.length - 1; out > 0; out--) { //n-1趟排序
		max = 0;
		for(in = 0; in <= out; in++ ) //每一趟找出最大值的下标
			max = in;
		if(theArray[in] > theArray[max]) { //在一趟排序的最后，将最大值放到数组的尾部
			tmp = theArray[in];
			theArray[in] = theArray[max];	
			theArray[max] = tmp;
		}
	}
}

插入排序

插入排序算法的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void insertSort(long[] theArray) {
	int out, in, ptr;
	long current;
	for(out = 1; out < theArray.length; i++) {
		current = theArray[out];
		ptr = out - 1;
		while(ptr >= 0 && current < theArray[p]) {
			theArray[ptr + 1] = theArray[ptr];
			ptr --;
		}
		theArray[ptr + 1] = current;
	}
}