对Java中的一些稳定算法进行了整理,使其符合自己的编程习惯。
package com.study.sort;
import java.util.LinkedList;
public class StableSort {
/**
* 生成一个随机数组
* @param length 数组长度
* @return 生成的数组
*/
public static int[] init(int length){
int [] before=new int[length];
Random rand=new Random(47);
for(int i=0;i<length;i++){
before[i]=rand.nextInt(100);
}
return before;
}
/**
* 插入排序
* @param before 待排序数组
* @return 排序后数组
*/
public static int[] insertSort(int[] before){
for(int j=1;j<before.length;j++){
int i=j-1;
int key=before[j];
while(i>=0&&key<before[i]){
before[i+1]=before[i];
i--;
}
before[i+1]=key;
}
return before;
}
/**
* 冒泡排序
* @param before 待排序数组
* @return 排序后数组
*/
public static int[] bubbleSort(int[] before){
int temp=0;
for(int i=before.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(before[j+1]<before[j]){
temp=before[j+1];
before[j+1]=before[j];
before[j]=temp;
}
}
}
return before;
}
/**
* 鸡尾酒排序(双向冒泡)
* @param before 待排序数组
* @return 排序后数组
*/
public static int[] cocktailSort(int[] before){
for(int i=0;i<(before.length/2);i++){
for(int j=i;j<before.length-i-1;j++){
if(before[j]>before[j+1]){
int temp=before[j+1];
before[j+1]=before[j];
before[j]=temp;
}
}
for(int j=(before.length-1-(i+1));j>i;j--){
if(before[j]<before[j-1]){
int temp=before[j];
before[j]=before[j-1];
before[j-1]=temp;
}
}
}
return before;
}
/**
* 归并排序
* @param before 待排序数组
* @return 排序后数组
*/
public static int[] mergeSort(int[] before){
recMergeSort(before,0,before.length-1);
return before;
}
public static void recMergeSort(int[] before,int lowerBound,int upperBound){
if(lowerBound==upperBound)
return;
else{
int mid=(lowerBound+upperBound)/2;
recMergeSort(before,lowerBound,mid);
recMergeSort(before,mid+1,upperBound);
merge(before,lowerBound,mid+1,upperBound);
}
}
public static void merge(int[] before,int lowerBound,int mid,int upperBound){
Queue<Integer> temp = new LinkedList<Integer>();
int indexA=lowerBound;
int indexB=mid;
while(indexA<=(mid-1)&&indexB<=upperBound){
if(before[indexA]<before[indexB])
temp.offer(before[indexA++]);
else
temp.offer(before[indexB++]);
}
while(indexA<=(mid-1))
temp.offer(before[indexA++]);
while(indexB<=upperBound)
temp.offer(before[indexB++]);
int index=0;
while(temp.size()>0){
before[lowerBound+index]=temp.poll();
index++;
}
}
/**
* 打印数组内容到控制台
* @param before 待显示数组
*/
public static void prt(int[] before){
for(int x:before){
System.out.print(x+" ");
}
System.out.println("");
}
public static void main(String[] args){
int[] before=init(10);
prt(before);
// insertSort(before);
// bubbleSort(before);
// cocktailSort(before);
mergeSort(before);
prt(before);
}
}
分享到:
相关推荐
几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...
几种经典的排序算法 (1)若n较小(如n≤50),可采用直接插入或直接选择排序。 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。 (2)若文件初始状态基本有序...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 (1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100(原始数据不...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 [需求分析] (1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100...
(1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
数据结构报告,包括插入排序(直接插入排序、希尔排序),交换排序(起泡排序、快速排序),选择排序(直接选择排序、堆排序),归并排序、分配排序的基本思想、复杂度分析以及稳定行分析。
【问题描述】在教科书中,各种排序算法的时间复杂度分析结果只给出了算法执行时间的渐进度,或者大概执行时间。试通过随机数据比较算法的关键字比较次数和关键字移动次数,以取得直观的感受。 【基本要求】(1)...
本问题要实现直接插入、冒泡、快速、简单选择、归并、堆排序六种排序算法的简单运用及比较,分析他们的稳定性及在不同规模下的复杂度,了解在什么情况下使用什么排序算法比较合适;待排序的元素好吗关键字为整数,...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
在进行时间复杂度比较时,我们通常关注几种主要情况: 1. **最坏情况时间复杂度(Worst-Case Time Complexity)**:这是在最不利的情况下,算法执行所需的时间。虽然这并不代表算法在所有情况下的表现,但它确保了...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
Python数据结构与算法(几种排序) 数据结构与算法(Python) 冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。...
希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次...
该项目包含Python中常见排序算法的几种实现。 算法名称 最好的 平均数 最差 记忆 稳定的 方法 泡泡排序 ñ n ^ 2 n ^ 2 1个 是的 交流中 计数排序 -- n + r n + r n + r 是的 不适用 循环排序 -- n ^ 2 n...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
快速排序是一种不稳定的排序,存在着优化空间,这里我们来看快速排序算法在Swift编程中的几种代码实现示例: