package sort;
public class SOrton {
public static void main(String[] args) {
int [] arrs = {6,1,2,7,9,3,4,5,10,8,3,4,6,10,43,2,12,66,66,1,77};
long a =System.currentTimeMillis();
//quickSort(arrs,0,arrs.length-1);
//bubbleSort(arrs);
//insertSort(arrs);
///selectSort(arrs);
mergeSort(arrs,0,arrs.length-1);
//shellSort(arrs,arrs.length);
long b =System.currentTimeMillis();
System.out.println("耗时 :"+(b-a));
for(int i = 0;i<arrs.length;i++) {
System.out.print(arrs[i]+" ");
}
}
/**
* 归并排序 (需要使用递归)
* @param arrs
* @param start 数组开始
* @param end 数组结束
*/
public static void mergeSort(int [] arrs,int start,int end) {
if(start<end) {
int mid = (end+start)/2;
mergeSort(arrs,start,mid);
mergeSort(arrs,mid+1,end);
merge(arrs,start,mid,end);
}
}
/**
*
* @param arrs
* @param left 序列数组开始
* @param mid 中间
* @param right 结束 如 [left,..mid] [mid+1,..right]
* [1,2] [3,4,5,6] 通过检测tmp =[1,2,..]
* 由于还有[3,4,5,6]没有参与检测 直接合并到 tmp={1,2,3,4,5,6}
*/
public static void merge(int arrs [] ,int left ,int mid,int right) {
int [] tmp = new int[arrs.length];//申请临时数组
int p1 = left,p2=mid+1,k=left;
while(p1<=mid && p2<=right) {
if(arrs[p1]<arrs[p2])
tmp[k++]=arrs[p1++];
else
tmp[k++]=arrs[p2++];
}
//还有没有检测比较的数据 直接 加在数组的后面(合并)
while(p1<=mid)
tmp[k++]=arrs[p1++];
while(p2<=right)
tmp[k++]=arrs[p2++];
//复制回原素组
for (int i = left; i <=right; i++)
arrs[i]=tmp[i];
}
/***
* 希尔排序
* @param arrs
* @param size
*/
public static void shellSort(int [] arrs,int size) {
if(size ==1)
return;
int s = size/2;
for(int i=s;i<arrs.length;i+=s) {
int j=i;
while(j>=s && arrs[j]<arrs[j-s]) {
int tmp =arrs[j];
arrs[j]=arrs[j-s];
arrs[j-s]=tmp;
j-=s;
}
}
shellSort(arrs,s);
}
/**
* 选择排序
* @param arrs
*/
public static void selectSort(int [] arrs) {
for(int i=0;i<arrs.length;i++) {
for(int j = i+1;j<arrs.length;j++) {
if(arrs[i]>arrs[j]) {
int tmp =arrs[j];
arrs[j]=arrs[i];
arrs[i]=tmp;
}
}
}
}
/***
* 插入排序
* @param arrs
*/
public static void insertSort(int arrs []) {
for(int i=1;i<arrs.length;i++) {
int j=i;
while(j>=1 && arrs[j]<arrs[j-1]) {
int tmp =arrs[j];
arrs[j]=arrs[j-1];
arrs[j-1]=tmp;
j--;
}
}
}
/***
* <h1>快速排序<h1>
* @param arrs
* @param left 开始的索引
* @param right 结束的索引
*
* 注意 只能从基数的对面开始 否则 如6,1,2,7,9 -->7,6,1,2,9 错误的结果
*
* 思想 :
* <br>
* 1、从由开始遍历,找到一个小于基数的则停下 i
* <br>
* 2、从左开始 找到大于基数的停止j
* <br>
* 3、 交换i和j
* <br>
* 4、若i==j 则 交换基数和i的值
* <br>
* 5、重复1-4
*
*/
public static void quickSort(int [] arrs,int left,int right) {
//选择一个数作为轴值
if(left>right)
return;
int key = arrs[left],i = left,j = right;
while(i!=j) {
while(key<=arrs[j] && i<j)
j--;
while(key>=arrs[i] && i<j)
i++;
if(i<j) {
int tmp = arrs[i];
arrs[i]=arrs[j];
arrs[j]=tmp;
}
}
arrs[left] = arrs[i];
arrs[i]=key;
quickSort(arrs,left,i-1);
quickSort(arrs,i+1,right);
}
/**
* <h1>冒泡排序<h1>
* @param arrs
*/
public static void bubbleSort(int arrs[]) {
for(int i=0;i<arrs.length;i++) {
for(int j = arrs.length-1;j>i;j--) {
if(arrs[j]<arrs[j-1]) {
int tmp = arrs[j];
arrs[j]=arrs[j-1];
arrs[j-1]=tmp;
}
}
}
}
}
分享到:
相关推荐
常见排序算法的实现 (插入排序、shell排序、堆排序、冒泡排序、快速排序、归并排序)
提供了Java实现几种常见排序方法和原理介绍
交换排序 插入排序 选择排序 堆排序 归并排序 比较统计排序 分布统计排序
详细讲述了8中常见算法的原理及思想,并用JAVA进行了实现,代码中有详细的注释,解释了算法的实现逻辑和一些小技巧。
五种常见排序法的比较 归并排序 快速排序 选择排序 插入排序 冒泡排序
常见排序算法的实现与性能比较JAVA 问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 实验要求: A. 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的排序样本(取值为[0...
几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...
包含了最常见的七种排序的动态演示,均为gif格式的,方便查看,也方便在制作课件的时候插入到课件当中,以便于给学生演示排序过程。 冒泡排序、插入排序、选择排序、快速排序、希尔排序、归并排序、堆排序。
冒泡排序等7种常见排序源代码
以下是用Python实现的五种常见排序算法: 1. 冒泡排序(Bubble Sort): ```python def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法
Java实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdf
常见排序算法的实现(一)-插入排序 常见排序算法的实现(二)-shell排序 常见排序算法的实现(三)-堆排序 常见排序算法的实现(四)-冒泡排序 常见排序算法的实现(五)-快速排序 常见排序算法的实现(六)→归并排序
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
Java数据挖掘18大算法实现和10大常见排序算法以及其他相关经典DM算法集合。 18大数据挖掘的经典算法以及代码实现,涉及到了决策分类,聚类,链接挖掘,关联挖掘,模式挖掘等等方面,后面都是相应算法的文章,希望能够...
关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见...
c++实现常见排序的模板:快排 堆排 折半 冒泡 选择 希尔 插入排序 可选择排序的数量 最终输出各种排序耗时
常见排序算法(JS版)