Java 数组排序

概要:

常用的排序方法有冒泡排序、快速排序、选择排序、插入排序、希尔(Shell)排序、堆排序。

| |目录

简介

冒泡排序是依次比较相邻的两个数,将大数放在前面,小数放在后面。即首先比较第一个和第二个数,将大数放前,小数放后。如此继续,直至比较最后两个数,将大数放前,小数放后。然后下一行再进行重复操作。

选择排序是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

插入排序(InsertionSort)把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素。在第一部分排序后,再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。

希尔排序(ShellSort)是插入排序的一种。基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<……<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

代码

package net.xsoftlab.baike;

public class TestSort {
	public static void bubbleSort(int[] x) {// 冒泡排序
		for (int i = 0; i < x.length; i++) {
			for (int j = i + 1; j < x.length; j++) {
				if (x[i] > x[j]) {// 将下标为i的数与下标为j的数进行比较
					int temp = x[i];// 元素交换
					x[i] = x[j];
					x[j] = temp;
				}
			}
		}
		for (int i = 0; i < x.length; i++) {// 循环将重新排序的结果输出
			System.out.print(x[i] + " ");
		}
	}

	public static void selectSort(int[] x) {// 选择排序
		for (int i = 0; i < x.length; i++) {
			int lowerIndex = i;
			for (int j = i + 1; j < x.length; j++) {// 循环找出最小的一个索引
				if (x[j] < x[lowerIndex]) {
					lowerIndex = j;
				}
			}
			int temp = x[i];// 交换
			x[i] = x[lowerIndex];
			x[lowerIndex] = temp;
		}
		for (int i = 0; i < x.length; i++) {// 循环将重新排序的结果输出
			System.out.print(x[i] + " ");
		}
	}

	public static void insertSort(int[] x) {// 插入排序
		for (int i = 1; i < x.length; i++) {// i从一开始,因为第一个数已经是排好序的
			for (int j = i; j > 0; j--) {
				if (x[j] < x[j - 1]) {
					int temp = x[j]; // 元素交换
					x[j] = x[j - 1];
					x[j - 1] = temp;
				}
			}
		}
		for (int i = 0; i < x.length; i++) {// 循环将重新排序的结果输出
			System.out.print(x[i] + " ");
		}
	}

	public static void shellSort(int[] x) {// 希尔排序
		for (int increment = x.length / 2; increment > 0; increment /= 2) {// 循环进行分组
			for (int i = increment; i < x.length; i++) {// 循环每个组内排序
				int temp = x[i];
				int j = 0;
				for (j = i; j >= increment; j -= increment) {
					if (temp < x[j - increment]) {// 元素进行判断、交换
						x[j] = x[j - increment];
					} else {
						break;
					}
				}
				x[j] = temp;
			}
		}
		for (int i = 0; i < x.length; i++) {// 循环将重新排序的结果输出
			System.out.print(x[i] + " ");
		}
	}

	public static void main(String[] args) {// java程序的主入口处
		int[] arr = { 1, 5, 6, 12, 4, 9, 3, 23, 39, 403, 596, 87 };
		System.out.println("----冒泡排序的结果:");
		bubbleSort(arr);// 调用冒泡排序方法
		System.out.println();
		System.out.println("----选择排序的结果:");
		selectSort(arr);// 调用选择排序方法
		System.out.println();
		System.out.println("----插入排序的结果:");
		insertSort(arr);// 调用插入排序方法
		System.out.println();
		System.out.println("----希尔(Shell)排序的结果:");
		shellSort(arr);// 调用希尔(Shell)排序
	}
}


评论关闭
评论 还能输入200
评论关闭
评论 还能输入200
资料加载中...
已关注 , 取消