各种排序算法python和java实现(一)

各种排序算法python和java实现(一)

先从最简单的实现冒泡排序：

# -*- coding: UTF-8 -*-
intarray=[3,4,5,1,2,0,6,9,7]
def bubble(array):
    for i in range(1,len(array)):
	    for j in range(i):
		    if array[j] > array[i]:
			    array[j],array[i] = array[i],array[j]
#遍历数组
def print_list(array):
    for i in intarray:
        print i,
#执行排序
bubble(intarray)
#打印
print_list(intarray);

存储为buble.py，命令行模式直接运行python buble.py

package sort;

public class Sort {
	public static void main(String[] args) {
		int[] array = new int[] { 3, 4, 5, 1, 2, 0, 6, 9, 7 };

		bubblesort(array);
		print(array);

	}

	private static void print(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]);
		}
	}

	private static void bubblesort(int[] array) {
		// 冒泡的趟数，为length - 1
		for (int i = 1; i < array.length; i++) {
			// 第二层循环为每次循环需要冒泡的次数
			for (int j = 0; j < i; j++) {
				if (array[j] > array[i]) {
					int temp = array[j];
					array[j] = array[i];
					array[i] = temp;
				}
			}
		}
	}
}

看完冒泡排序，看一个稍微有点思考的算法，直接插入排序，这种算法适合待排序的集合部分有序，先给出java的实现方式：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">/** * 假设当前某个子集有序，选择下个值插入到这个有序的子集中 整个过程主要在于寻找要插入的下标。插入排序在部分子集有序 的情况下非常快。 * 初始假设array[0]有序 * @param array */ private static void insertSort(int[] array) { // 默认第一个为有序 int length = array.length; int temp; int j; // 将当前的值插入到有序子集 for (int i = 1; i < length; i++) { // 如果当前值比有序子集的最大值小则执行交换 if (array[i] < array[i - 1]) { // temp存储当前要插入的值，也叫做哨兵 temp = array[i]; // 有序子集从0-j，从后向前遍历 for (j = i - 1; j >= 0; j--) { if (temp < array[j]) { // 如果哨兵值小于子集的当前值，则将子集的当前值后移 array[j + 1] = array[j]; } else { // 否则找到哨兵要插入的下标 break; } } // 插入的下标为j+1 array[j + 1] = temp; } } }

下面是python的实现：

def insertSort(array):
	length = len(array)
	for i in range(1,length):
		if array[i] < array[i-1]:
			temp=array[i]
			for j in range(0,i)[::-1]:
				if temp < array[j]:
					array[j+1] = array[j]
				else:
					j = j+1
					break
			array[j] = temp

看完直接排序，再来看下选择排序，顾名思义选择排序，每次遍历选择出子集的最小值，看java实现：

/**
	 * 选择排序,每趟选择出子集的最小值，然后交换
	 * 
	 * @param array
	 */
	public static void selectionSort(int[] array) {
		int temp, minIndex;
		for (int i = 0; i < array.length; i++) {
			// 假设初始最小值为子集的第一个元素
			minIndex = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[minIndex] > array[j]) {
					// 找出最小值的下标
					minIndex = j;
				}
			}
			if (minIndex != i) {
				// 交换
				temp = array[i];
				array[i] = array[minIndex];
				array[minIndex] = temp;
			}
		}
	}

再来看python版本：

def selectionSort(array):
	for i in xrange(0,len(array)):
		index = i
		for j in xrange(i,len(array)):
			if array[index] > array[j]:
				index = j
		temp = array[i]
		array[i] = array[index]
		array[index] = temp

以上就是集中简单排序的java和python实现，下一篇讲解几个稍微复杂点得变形排序。