首页 > 代码库 > java排序算法总结
java排序算法总结
java的排序算法有：插入排序（直接插入排序，希尔排序），选择排序（直接选择排序，堆排序），交换排序（冒泡排序，快速排序），归并排序，基数排序
java排序算法比较的多，每个算法有各自的优点和缺点，对于选择什么样的排序算法，这要依照问题的规模和数据是否有序进行选择比较好的排序算法。
以下是各种排序算法的总结代码：
冒泡排序：
package com.wj.interview;
import java.util.Arrays;
import java.util.Scanner;
//请用Java写一个冒泡程序，要求输入10个整数，输出排序结果
public class InterviewSort1 {
/**
* @param args
*/
//得到输入流
public static Scanner getScnner(){
Scanner scanner=new Scanner(System.in);
return scanner;
}
//返回输入的整数
public static int getInt(Scanner scanner){
int num=scanner.nextInt();
return num;
}
/*
* 交换排序的思想是：两两比较待排序记录的关键字，发现两个记录的次序相反即进行交换排序
* ，直到没有反序的记录为止。交换排序有冒泡排序和快速排序
* 冒泡排序属于交换排序，是稳定的排序算法。*/
//进行冒泡排序的函数，冒泡排序的最好时间度为O(n),最好和平均为O(n^2)
public static void sortArray(int array[]){
int temp;//交换的中间变量
int count=0;//进行循环的次数
boolean flag=false;//标志变量，如果数组有序了则flag为true不在进行循环了
for(int i=0;i<array.length-1&&!flag;i++){
flag=true;
for(int j=0;j<array.length-i-1;j++){
count++;
if(array[j]>array[j+1]){
temp = array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=false;
}
}
}
System.out.println("count:"+count+";"+Arrays.toString(array));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int array[]=new int[]{2,1,6,5,44,34,7,22,12,10};
int array[]=new int[10];
Scanner sc=getScnner();
System.out.println("请输入10个整数，进行排序：");
for(int i=0;i<10;i++){
array[i]=getInt(sc);
}
System.out.println("你输入的10个数为：");
System.out.println(Arrays.toString(array));
System.out.println("--------------------");
sortArray(array);
System.out.println("排序后的结果为：");
System.out.println(Arrays.toString(array));
}
}
快速排序：
package com.wj.interview;
import java.util.Arrays;
import java.util.Scanner;
//请用Java写一个冒泡程序，要求输入10个整数，输出排序结果
public class InterviewSort1 {
/**
* @param args
*/
//得到输入流
public static Scanner getScnner(){
Scanner scanner=new Scanner(System.in);
return scanner;
}
//返回输入的整数
public static int getInt(Scanner scanner){
int num=scanner.nextInt();
return num;
}
/*
* 交换排序的思想是：两两比较待排序记录的关键字，发现两个记录的次序相反即进行交换排序
* ，直到没有反序的记录为止。交换排序有冒泡排序和快速排序
* 冒泡排序属于交换排序，是稳定的排序算法。*/
//进行冒泡排序的函数，冒泡排序的最好时间度为O(n),最好和平均为O(n^2)
public static void sortArray(int array[]){
int temp;//交换的中间变量
int count=0;//进行循环的次数
boolean flag=false;//标志变量，如果数组有序了则flag为true不在进行循环了
for(int i=0;i<array.length-1&&!flag;i++){
flag=true;
for(int j=0;j<array.length-i-1;j++){
count++;
if(array[j]>array[j+1]){
temp = array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=false;
}
}
}
System.out.println("count:"+count+";"+Arrays.toString(array));
}
//快速排序是一种二叉树结构的交换排序算法
//快速排序算法的最好情况下的时间复杂度为O(nlbn),最坏为O(n*n),平均时间复杂度为O(nlbn)
//快速排序算法的最坏情况的空间复杂度为O(n),快速排序算法是一种不稳定的排序算法
public static void quickSort(int array[],int low,int hight){
//low为数组的低端下标,hight为数组的高端下标
int i=low,j=hight;
int temp=array[low];//取第一元素为标准数据元素
while(i<j){
while(i<j&&temp<=array[j]){//在数组的右端扫描
j--;
}
if(i<j){
array[i]=array[j];
i++;
}
while(i<j&&temp>array[i]){//在数组的左端扫描
i++;
}
if(i<j){
array[j]=array[i];
j--;
}
}
array[i]=temp;
if(low<i){
quickSort(array,low,i-1);//对左子集合进行递归
}
if(i<hight){
quickSort(array,j+1,hight);//对右子集合进行递归
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]=new int[]{2,1,6,5,44,34,7,22,12,10};
int array2[]=new int[]{2,1,6,5,44,34,7,22,12,10};
/*int array[]=new int[10];
Scanner sc=getScnner();
System.out.println("请输入10个整数，进行排序：");
for(int i=0;i<10;i++){
array[i]=getInt(sc);
}*/
System.out.println("你输入的10个数为：");
System.out.println(Arrays.toString(array));
System.out.println("--------------------");
sortArray(array);
System.out.println("冒泡排序后的结果为：");
System.out.println(Arrays.toString(array));
System.out.println("---------------------------");
quickSort(array2,0,9);
System.out.println("快速排序后的结果为：");
System.out.println(Arrays.toString(array));
}
}
输出结果：
你输入的10个数为：
[2, 1, 6, 5, 44, 34, 7, 22, 12, 10]
--------------------
count:35;[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
冒泡排序后的结果为：
[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
---------------------------
快速排序后的结果为：
[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
直接选择排序：
package com.wj.interview;
import java.util.Arrays;
import java.util.Scanner;
//请用Java写一个选择排序程序，要求输入10个整数，输出排序结果
public class InterviewSort2 {
/**
* @param args
*/
//得到输入流
public static Scanner getScnner(){
Scanner scanner=new Scanner(System.in);
return scanner;
}
//返回输入的整数
public static int getInt(Scanner scanner){
int num=scanner.nextInt();
return num;
}
/*选择排序是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中
* 找到最小元素，存放到排序列的起始位置，然后，在从剩余未排序元素中继续寻找最小元素，放
* 放到排序序列末尾。以此类推，直到所有的元素均排序完毕。
* 选择排序有直接选择排序和堆排序。
* */
//进行选择排序的函数
//直接选择排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)，直接选择排序是不稳定的算法
public static void sortArray(int array[]){
int small,temp;
for(int i=0;i<array.length-1;i++){
small=i;//设第i个数据元素关键字最小
for(int j=i+1;j<array.length;j++){//寻找最小的数据元素
if(array[j]<array[small]){
small=j;//记住最小元素的下标
}
}
if(small!=i){//当最小元素的下表不为i时交换位置
temp=array[i];
array[i]=array[small];
array[small]=temp;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]=new int[]{2,1,6,5,44,34,7,22,12,10};
/*int array[]=new int[10];
Scanner sc=getScnner();
System.out.println("请输入10个整数，进行排序：");
for(int i=0;i<10;i++){
array[i]=getInt(sc);
}*/
System.out.println("你输入的10个数为：");
System.out.println(Arrays.toString(array));
System.out.println("--------------------");
sortArray(array);
System.out.println("直接选择排序后的结果为：");
System.out.println(Arrays.toString(array));
}
}
输出结果：
你输入的10个数为：
[2, 1, 6, 5, 44, 34, 7, 22, 12, 10]
--------------------
直接选择排序后的结果为：
[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
插入排序算法：
package com.wj.interview;
import java.util.Arrays;
import java.util.Scanner;
//请用Java写一个插入排序程序，要求输入10个整数，输出排序结果
public class InterviewSort3 {
/**
* @param args
*/
//得到输入流
public static Scanner getScnner(){
Scanner scanner=new Scanner(System.in);
return scanner;
}
//返回输入的整数
public static int getInt(Scanner scanner){
int num=scanner.nextInt();
return num;
}
/*插入排序的基本思想：从初始有序的子集合中，不断地把新的数据元素插入到已排列有序子集合的合适位置，使
* 子集合中数据元素的个数不断增多，当子集合等于集合时，插入排序算法结束。常用的插入排序有直接插入排序和希尔排序两种。
*
* 选择排序有直接选择排序和堆排序。
* */
/*直接插入排序的基本思想：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据子集合的适当位置。子集合的数据元素个数从只有一个
* 数据元素开始，逐次增大，当子集合大小最终和集合大小相同时，排序完毕。
* 最好的情况下时间复杂度为O(n),最好情况为O(n^2)，原始数据元素集合越接近有序，直接插入排序的时间效率越好
* 空间复杂度为O(1),直接插入排序是一种稳定的排序算法。
* */
public static void sortArray(int array[]){
int temp,j;
for(int i=0;i<array.length-1;i++){//进行n-1次插入
temp=array[i+1];
j=i;
while(j>-1&&temp<array[j]){//查找适当的位置
array[j+1]=array[j];
j--;
}
array[j+1]=temp;//进行插入
}
}
////请用Java写一个希尔排序程序，要求输入10个整数，输出排序结果
/*
* 希尔排序的基本思想：把待排序的数据元素分成若干个小组，对同一个小组内的数据元素用直接插入法排序；小组的个数逐次
* 减少；当完成了所有数据元素都在一个组内的排序后，排序过程结束。希尔排序有称作缩小增量排序。
*
* 希尔排序的时间复杂度较直接插入排序算法的时间复杂度改善很多，希尔排序的时间取决与各次排序时增量的个数
* 和增量的取值。若取值比较合理，则希尔排序算法的时间复杂度约为O(n(lbn)*(lbn))，空间复杂度为O(1);
* 希尔排序算法是按增量分组进行排序的，所以希尔排序算法是一种不稳定的排序算法
* */
public static void shell(int array[],int d[]){
//用希尔排序法对数据元素array[]进行排序，d[]为排序的增量值
int span,temp,j;//
for(int m=0;m<d.length;m++){//循环的次数为分的组数
span=d[m];//每次的增量值
for(int k=0;k<span;k++){
//组内是直接插入排序，区别是每次不是增加1而是增加span
for(int i=k;i<array.length-span;i=i+span){
temp=array[i+span];
j=i;
while(j>-1&&temp<array[j]){
array[j+span]=array[j];
j=j-span;
}
array[j+span]=temp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]=new int[]{2,1,6,5,44,34,7,22,12,10};
int array2[]=new int[]{2,1,6,5,44,34,7,22,12,10};
int d[]=new int[]{4,3,2,1};
/*int array[]=new int[10];
Scanner sc=getScnner();
System.out.println("请输入10个整数，进行排序：");
for(int i=0;i<10;i++){
array[i]=getInt(sc);
}*/
System.out.println("你输入的10个数为：");
System.out.println(Arrays.toString(array));
System.out.println("--------------------");
sortArray(array);
System.out.println("直接插入排序后的结果为：");
System.out.println(Arrays.toString(array));
System.out.println("-----------------------");
shell(array2,d);
System.out.println("希尔排序后的结果:");
System.out.println(Arrays.toString(array2));
}
}
输出结果：
你输入的10个数为：
[2, 1, 6, 5, 44, 34, 7, 22, 12, 10]
--------------------
直接插入排序后的结果为：
[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
-----------------------
希尔排序后的结果:
[1, 2, 5, 6, 7, 10, 12, 22, 34, 44]
归并排序：
package com.wj.interview;
import java.util.Arrays;
import java.util.Scanner;
//请用Java写一个归并排序程序，要求输入10个整数，输出排序结果
public class InterviewSort4 {
/**
* @param args
*/
//得到输入流
public static Scanner getScnner(){
Scanner scanner=new Scanner(System.in);
return scanner;
}
//返回输入的整数
public static int getInt(Scanner scanner){
int num=scanner.nextInt();
return num;
}
/*归并排序的基本思想：设数组a中有n个数据元素，初始时把它们看成式n个长度为1的有序子数组，
*然后从第一个有序子数组开始，把相邻的有序子数组两两合并，得到取整[n/2]个长度为2的新的有
* 序子数组（当n为奇数时，最后一个新的有序子数组的长度为1）。对这些新的有序子数组进行两两
*归并。如此重复，直到得到一个长度为n的有序数组为止。
* */
/*一次二路归并排序算法如下：
* */
public static void merge(int array[],int swap[],int k){
//k为有序子数组的长度,一次二路归并排序后的有序子序列存于数组swap中
int lowfirst=0;//第一个有序子数组下界为0
int hightfirst;//第一个有序子数组上界
int lowseconde;//第二个子数组的上界
int hightseconde;//第二个有序子数的下界
int m=0,i,j;
while(lowfirst+k<=array.length-1){
lowseconde=lowfirst+k;//计算第二个有序子数组下界
hightfirst=lowseconde-1;//计算第一个有序子数组上界
//计算第二个有序子数组上界
hightseconde=(lowseconde+k-1<=array.length-1)?lowseconde+k-1:array.length-1;
//两个有序子数组合并
for(i=lowfirst,j=lowseconde;i<=hightfirst&&j<=hightseconde;m++){
if(array[i]<=array[j]){
swap[m]=array[i];
i++;
}else{
swap[m]=array[j];
j++;
}
}
//子数组2已经归并完，将子数组1中剩余的元素存放到数组swap中
while(i<=hightfirst){
swap[m]=array[i];
m++;
i++;
}
//子数组1已经归并完，将子数组2中剩余的元素存放到数组swap中
while(j<=hightseconde){
swap[m]=array[j];
m++;
j++;
}
lowfirst=hightseconde+1;
}
//将原始数组中只够一组的数据元素顺序放到数组swap中
for(i=lowfirst;i<array.length;i++,m++){
swap[m]=array[i];
}
}
//二路归并排序算法如下：
//二路归并排序的时间复杂度为O(nlbn),空间复杂度为O(n)，二路归并排序不仅是时间复杂度是O(nlbn)而且还是是一种稳定的排序算法
//（这是二路归并排序算法的最大特点）
public static void mergeSort(int array[]){
int k=1;//归并长度从1开始
int swap[]=new int[array.length];
while(k<array.length){
merge(array,swap,k);//调用归并函数
for(int i=0;i<array.length;i++){
array[i]=swap[i];//将元素从临时数组swap放回数组array中
}
k=k*2;//归并长度加倍
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]=new int[]{2,1,6,5,44,34,7,22,12,10};
int array2[]=new int[]{2,1,6,5,44,34,7,22,12,10,-2,90,-3};
int d[]=new int[]{4,3,2,1};
/*int array[]=new int[10];
Scanner sc=getScnner();
System.out.println("请输入10个整数，进行排序：");
for(int i=0;i<10;i++){
array[i]=getInt(sc);
}*/
System.out.println("你输入的10个数为：");
System.out.println(Arrays.toString(array));
System.out.println("--------------------");
mergeSort(array2);
System.out.println("归并排序后的结果为：");
System.out.println(Arrays.toString(array2));
System.out.println("-----------------------");
}
}
输出结果：
你输入的10个数为：
[2, 1, 6, 5, 44, 34, 7, 22, 12, 10]
--------------------
归并排序后的结果为：
[-3, -2, 1, 2, 5, 6, 7, 10, 12, 22, 34, 44, 90]
-----------------------
本文原创，来自：http://blog.csdn.net/j903829182/article/details/38566457
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。