关于Java排序算法-归并排序(Merge Sort)

关于Java排序算法-归并排序(Merge Sort)

二路归并排序的基本思想:设 n 个待排记录,看成是 n 个有序的子序列,每个子序列的长度为 1 ,对此进行两两归并,得到 n/2 个长度为 2 或 1 的有序子序列;再继续两两归并,得到 n/4 个有序子序列,重复进行直至得到一个长度为 n 的有序序列为止。

public class MergeSort {

public static void main(String[] args) {

//int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; [阅读全文]

关于Java排序算法-堆排序(Heap Sort)

关于Java排序算法-堆排序(Heap Sort)

堆排序是利用堆的特性进行排序的过程。

堆排序:输出堆顶的最小(大)值后,使剩余的n-1个元素序列重新再建成堆,则可得到原序列的次小(大)值。反复进行可得到一个有序序列,整个过程称为堆排序。

堆排序分为两个步骤:

根据初始输入数据,形成初始堆;

通过一系列的记录交换和重新调整堆进行排序。

public class HeapSort {

// 主函数

public static void main(String[] args) {

int[] arr = { 2 [阅读全文]

关于Java排序算法-希尔排序(Shell Sort)

关于Java排序算法-希尔排序(Shell Sort)

希尔排序又称“缩小增量排序”,是通过对直接插入排序进行改进得到的一种插入排序法。

基本思想:将整个待排序列分割成几个较小的子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对整个记录序列进行一次直接插入排序。

过程:设待排序列有n个记录, 首先取一个整数d1< n 作为步长, 将全部记录分为d1个子序列, 所有距离为d1的记录放在同一个子序列中, 在每个子序列中分别施行直接插入排序。然后缩小步长 , 如取 d2=d1/2,重复上述的子序列划分和排序工作。直到最后取dt=1 [阅读全文]

关于Java排序算法-快速排序(Quick Sort)

关于Java排序算法-快速排序(Quick Sort)

快速排序是对气泡排序的一种改进。

基本思想:通过一趟排序将待排序列分割成独立的两部分,其中一部分元素的排序码均比另一部分的排序码小,分别对这两部分继续进行排序,直至整个序列有序。

具体过程:设待排序列为 A[s..t],选取任意一个元素作为支点(基准元素,一般就选A[s]),然后从区间两端向中间依次比较元素,一旦发现前半部分有元素大于基准元素,后半部分有元素小于基准元素,则交换这两个元素,所有元素比较一遍后,最后把基准元素交换到两部分的中间,使得所有比基准元素大的都排在此基准元素的后面; [阅读全文]

关于Java排序算法-直接选择排序(Select Sort)

关于Java排序算法-直接选择排序(Select Sort)

基本思想:每一趟排序,如第 i 趟 ( i = 0, 1, …, n-2) ,均在 待排序记录中选出排序码最小的记录, 作为有序序列中的第 i 个记录。包括直接选择排序和堆排序。

基本操作:第一趟从n个记录中选出排序码最小的记录与第1个记录交换;第二趟在余下的n-1个记录中再选出排序码最小的记录与第2个记录交换;依次类推,直至第n-1趟选出相应记录与第n-1个位置上的记录交换。

public class SortTest {

public static void main(St [阅读全文]

关于Java排序算法-直接插入排序(Insert Sort)

关于Java排序算法-直接插入排序(Insert Sort)

基本思想:当插入第i (i ≥ 1) 个记录时, 前面的A[0], A[1], …, A[i-1]已经排好序。这时, 用A[i]的排序码与A[i-1], A[i-2], …的排序码顺序进行比较, 找到插入位置即将A[i]插入, 原来位置上的记录向后顺移。

过程:首先将待排序序列的第 1 个数据元素看成是一个有序的子序列,然后依次将第 2 个数据元素、第 3 个数据元素、…… 插入到这个有序序列。

public class SortTest {

public static voi [阅读全文]