|
排序法 |
最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
| 选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 归并排序 | O(n^2) | O(n*logn) | 稳定 | 不一定 |
| 希尔排序 | O(n*(logn)2) | O(n*(logn)2) | 不稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 基数排序 | O(kn) | O (nlog(r)m) | 稳定 | O(kn) |
import java.util.ArrayList;
import java.util.Iterator;
public class sort {
//选择排序
public int[] sort1(int[] arr){
for (int i = 0; i < arr.length; i++) {
int temp,pos=i;
int mininum=arr[i];
for (int j = i; j < arr.length; j++) {
if (mininum >arr[j]) {
mininum=arr[j];
pos=j;
}
}
temp=arr[i];
arr[i]=mininum;
arr[pos]=temp;
}
return arr;
}
//冒泡排序
public int[] sort2(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
int temp;
for (int j = 0; j < arr.length-1-i; j++) {
if (j+1==arr.length-i) {
break;
}else {
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
return arr;
}
//二分插入排序(递归)
public int[] sort3(int[] arr,int begin,int end){
if (end==1) {
return arr;
}else {
arr=sort3(arr, begin, end/2);
for (int i = end/2; i < end; i++) {
int temp;
for (int j = 0; j < i; j++) {
if (arr[i]<=arr[j]) {
temp=arr[i];
for (int k = i-1; k >j-1; k--) {
arr[k+1]=arr[k];
}
arr[j]=temp;
}else {
}
}
}
}
return arr;
}
//二分插入排序(递归)
public static ArrayList<Integer> sort3integer(ArrayList<Integer> arr,int begin,int end){
if (end==1) {
return arr;
}else {
arr=sort3integer(arr, begin, end/2);
for (int i = end/2; i < end; i++) {
int temp;
for (int j = 0; j < i; j++) {
if (arr.get(i)<=arr.get(j)) {
temp=arr.get(i);
for (int k = i-1; k >j-1; k--) {
arr.set(k+1,arr.get(k));
}
arr.set(j, temp);
}else {
}
}
}
}
return arr;
}
//直接插入排序
public int[] sort4(int[] arr){
for (int i = 1; i < arr.length; i++) {
int temp;
for (int j = 0; j < i; j++) {
if (arr[i]>arr[j]) {
}else {
temp=arr[i];
for (int k = i-1; k >j-1; k--) {
arr[k+1]=arr[k];
}
arr[j]=temp;
}
}
}
return arr;
}
//希尔排序（递归）
public int[] sort5(int[] arr,int gap){
if(gap==1){
arr=sort3(arr, 0, arr.length);
return arr;
}else {
int gap1=(gap%2==1?gap/2+1:gap/2);
ArrayList<Integer>list=new ArrayList<Integer>();
ArrayList<Integer>poslist=new ArrayList<Integer>();
for (int i = 0; i < gap; i++) {//对每一个子序列进行插入排序
int temp2=i;
while(temp2<arr.length){
poslist.add(temp2);
list.add(arr[temp2]);
temp2+=gap;
}
list=sort3integer(list, 0, list.size());
for (int j = 0; j < list.size(); j++) {
arr[poslist.get(j).intValue()]=list.get(j);
}
list.clear();
poslist.clear();
}
printlist(arr);
System.out.println("-->");
arr=sort5(arr, gap1);
}
return arr;
}
//归并排序
public ArrayList<Integer> sort6(ArrayList<Integer> arr,int begin,int end){
if (begin==end-1) {
return arr;
}else {
int mid=(begin+end)/2;
ArrayList<Integer>arr1=new ArrayList<Integer>();
ArrayList<Integer>arr2=new ArrayList<Integer>();
for(int i=begin;i<mid;i++){
arr1.add(arr.get(i));
}
for(int i=mid;i<end;i++){
arr2.add(arr.get(i));
}
arr=merge(sort6(arr1, begin, mid),sort6(arr2, 0, end-mid));
return arr;
}
}
//快速排序
public ArrayList<Integer> sort7(ArrayList<Integer> arr,int begin,int end){
if (begin==end-1||end==begin) {
return arr;
}else {
int temp=0,key=arr.get(begin),i=begin,j=end-1;
while (i!=j) {
while(arr.get(j)>=key){
if (j>begin) {
j--;
}
if (i==j) {
break;
}
}
if (i==j) {
break;
}
temp=arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, temp);
while(arr.get(i)<key){
if (i<end-1) {
i++;
}
if (i==j) {
break;
}
}
if (i==j) {
break;
}
temp=arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, temp);
}
sort7(arr,0,i);
sort7(arr,i+1,end);
return arr;
}
}
//堆排序
public int[] sort8(int[] arr){
if (arr.length==1) {
return arr;
}else {
for(int i=0;i<arr.length;i++){
int temp=0,leftChild=-1,rightChild=-1,end=arr.length-i;
if (end>1) {//有左孩子
leftChild=1;
}
if (end>2) {//有右孩子
rightChild=2;
}
getMaxHeap(arr, leftChild, rightChild, end);
temp=arr[0];
arr[0]=arr[end-1];
arr[end-1]=temp;
}
return arr;
}
}
//基数排序
public ArrayList<Integer> sort9(ArrayList<Integer> arr,int radix){
ArrayList<ArrayList<Integer>> binarr=new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer>tmpArrayList=new ArrayList<Integer>();
binarr.add(tmpArrayList);
}
int rd=1,ra=1;
while(true){
rd*=10;
if (ra>radix) {
break;
}
for (int i = 0; i < arr.size(); i++) {
switch((arr.get(i)%rd)/(rd/10)){
case 0:
binarr.get(0).add(arr.get(i));
break;
case 1:
binarr.get(1).add(arr.get(i));
break;
case 2:
binarr.get(2).add(arr.get(i));
break;
case 3:
binarr.get(3).add(arr.get(i));
break;
case 4:
binarr.get(4).add(arr.get(i));
break;
case 5:
binarr.get(5).add(arr.get(i));
break;
case 6:
binarr.get(6).add(arr.get(i));
break;
case 7:
binarr.get(7).add(arr.get(i));
break;
case 8:
binarr.get(8).add(arr.get(i));
break;
case 9:
binarr.get(9).add(arr.get(i));
break;
}
}
arr.clear();
for(int i=0;i<10;i++){
for (int k = 0; k < binarr.get(i).size(); k++) {
arr.add(binarr.get(i).get(k));
}
binarr.get(i).clear();
}
ra++;
}
return arr;
}
//构造最大堆
public static int[] getMaxHeap(int[] arr,int leftChild,int rightChild,int end){
if (leftChild==-1&&rightChild==-1||rightChild==0) {//rightChild==0防止把最终父节点作为一个右孩子处理
return arr;
}else {
int lleftChild=-1,rrightChild=-1,rleftChild=-1,lrightChild=-1;
//左孩子的子节点
if (leftChild*2+1<end) {
lleftChild=leftChild*2+1;
}
if (leftChild*2+2<end){
lrightChild=leftChild*2+2;
}
//右孩子的子节点
if (rightChild*2+1<end) {
rleftChild=rightChild*2+1;
}
if (rightChild*2+2<end){
rrightChild=rightChild*2+2;
}
if (leftChild!=-1&&rightChild!=-1) {
int parent=(leftChild-1)/2,temp=0;
while(parent>=0){
temp=arr[parent];
if (arr[leftChild]>arr[rightChild]) {
if (arr[leftChild]>arr[parent]) {
arr[parent]=arr[leftChild];
arr[leftChild]=temp;
}
}else {
if (arr[rightChild]>arr[parent]) {
arr[parent]=arr[rightChild];
arr[rightChild]=temp;
}
}
if(parent%2==1){//位于父节点的左孩子处
leftChild=parent;
rightChild=parent+1;
}else {//位于父节点的右孩子处
leftChild=parent-1;
rightChild=parent;
}
parent=(leftChild-1)/2;
}
}else {
if (leftChild!=-1&&rightChild==-1) {//只会出现只有左孩子没有右孩子的情况，不会出现相反的情况
int parent=(leftChild-1)/2,temp=0;
temp=arr[parent];
if (arr[leftChild]>arr[parent]) {
arr[parent]=arr[leftChild];
arr[leftChild]=temp;
}
if(parent%2==1){//位于上一个的左孩子处
leftChild=parent;
rightChild=parent+1;
}else {
leftChild=parent-1;
rightChild=parent;
}
parent=(leftChild-1)/2;
while(parent>=0){
temp=arr[parent];
if (arr[leftChild]>arr[rightChild]) {
if (arr[leftChild]>arr[parent]) {
arr[parent]=arr[leftChild];
arr[leftChild]=temp;
}
}else {
if (arr[rightChild]>arr[parent]) {
arr[parent]=arr[rightChild];
arr[rightChild]=temp;
}
}
if(parent%2==1){//位于父节点的左孩子处
leftChild=parent;
rightChild=parent+1;
}else {//位于父节点的右孩子处
leftChild=parent-1;
rightChild=parent;
}
parent=(leftChild-1)/2;
}
}else {
}
}
getMaxHeap(arr, lleftChild, lrightChild, end);
getMaxHeap(arr, rleftChild, rrightChild, end);
return arr;
}
}
//合并两个有序子序列并返回一个有序的序列
public static ArrayList<Integer> merge(ArrayList<Integer>list1,ArrayList<Integer>list2){
ArrayList<Integer>newList=new ArrayList<Integer>();
if (list1==null||list1.size()==0) {
return list2;
}
if (list2==null||list2.size()==0) {
return list1;
}
if(list1.get(list1.size()-1)<=list2.get(0)){
newList.addAll(list1);
newList.addAll(list2);
}else {
if (list2.get(list2.size()-1)<=list1.get(0)) {
newList.addAll(list2);
newList.addAll(list1);
}else {
Iterator<Integer>iterator1=list1.iterator();
Iterator<Integer>iterator2=list2.iterator();
boolean flag=true;
Integer num1=iterator1.next();
Integer num2=iterator2.next();
if (num1<num2) {
newList.add(num1);
flag=true;
}else {
newList.add(num2);
flag=false;
}
while (true) {
if (flag) {
if (!iterator1.hasNext()) {
break;
}
num1=iterator1.next();
}else {
if (!iterator2.hasNext()) {
break;
}
num2=iterator2.next();
}
if (num1<num2) {
newList.add(num1);
flag=true;
}else {
newList.add(num2);
flag=false;
}
}
if (flag) {
newList.add(num2);
}else {
newList.add(num1);
}
while (iterator1.hasNext()) {
newList.add(iterator1.next());
}
while (iterator2.hasNext()) {
newList.add(iterator2.next());
}
}
}
return newList;
}
//打印数组
public void printlist(int [] arr){
System.out.println("the result:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"->");
}
System.out.println("END");
}
//打印list
public void printlist2(ArrayList<Integer> arr){
System.out.println("the result:");
for (int i = 0; i < arr.size(); i++) {
System.out.print(arr.get(i)+"->");
}
System.out.println("END");
}
public static void main(String args[]){
sort mysort=new sort();
int arr[]={4,3,22,565,2,566,77,5,3,9};
ArrayList<Integer>list=new ArrayList<Integer>();
list.add(4);list.add(3);list.add(22);list.add(565);list.add(2);list.add(566);list.add(77);list.add(5);list.add(3);list.add(9);
// mysort.printlist(mysort.sort1(arr));
// mysort.printlist(mysort.sort2(arr));
// mysort.printlist(mysort.sort3(arr,0,arr.length));
// mysort.printlist(mysort.sort4(arr));
// mysort.printlist2(mysort.sort3integer(list, 0, list.size()));
// int gap1=arr.length%2==1?arr.length/2+1:arr.length/2;
// mysort.printlist(mysort.sort5(arr,gap1));
// mysort.printlist2(mysort.sort6(list,0,list.size()));
mysort.printlist2(mysort.sort7(list,0,list.size()));
// mysort.printlist(mysort.sort8(arr));
// mysort.printlist2(mysort.sort9((list),3));
}
}
相关推荐
Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...
java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法...
JAVA算法编程题目及答案 本资源提供了50道JAVA算法编程题目及答案，涵盖了算法设计、数据结构、程序设计等多个方面的知识点。以下是对标题、描述、标签和部分内容的详细解释： 标题：JAVA算法编程题目及答案 本...
Java算法全卷涵盖了基本算法和图算法，是学习和提升编程技能的重要资源。这份资料主要针对使用Java语言进行算法实现的开发者，适用于那些对ANT、EJB、J2EE、JAVA和SPRING等技术栈有了解或兴趣的人群。下面我们将深入...
从给定的文件信息来看，标题“Java算法PDF版”暗示了这是一份关于Java编程语言中的算法应用和实现的资料。尽管描述部分没有提供太多具体的信息，仅表达了分享的意愿，但我们可以根据标题和可能包含的内容来深入探讨...
Java算法设计涵盖了许多核心编程概念，是解决复杂问题的关键工具。这个压缩包文件包含了各种算法的实现，让我们逐一探讨它们。 1. **排序算法**：排序是数据处理的基础，这里可能包括了各种经典排序算法，如快速...
java算法分析与设计之集装箱装载问题源代码 算法作为计算机专业学生的必修课，同时也是软件开发过程中必备的编程思想，对学习研究计算机专业意义重大；正因为这门课程难，所以除了相关方面的书籍，网络资源少的可怜,...
《Java算法设计与题解》是一本专注于Java编程语言中的算法设计和问题解决的书籍，旨在帮助读者深入理解和掌握各种经典算法，并通过编程实例来提升实际应用能力。书中的内容涵盖了算法的基础理论、核心思想以及在Java...
本文将深入探讨“JAVA算法分析”，旨在帮助读者从深层次理解Java语言，并结合算法思想提升编程能力。 首先，Java语言为实现高效算法提供了良好的支持。其面向对象的特性使得代码更易于组织和复用，接口、抽象类和...
本篇文章将深入探讨数据挖掘的Java算法，以及如何利用Java进行高效的数据分析。 一、数据预处理 数据预处理是数据挖掘的第一步，包括数据清洗、数据集成、数据转换和数据规约。在Java中，可以使用Apache Commons ...
《实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划、HashTable算法)》 课程简介： 算法分析与设计Java版，是一套实用型算法课程。通过本课程的学习，学员可以掌握以下技术点:线性结构与顺序表...
本篇文章将详细探讨基于Java的算法实践，主要以"java算法练习代码code"为背景，深入解析其中可能涵盖的知识点。 首先，我们需要理解算法的基本概念。算法是一系列明确的步骤，用于解决特定问题或执行特定任务。在...
java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用数据结构java算法大全，常用...
本资源“Java算法刷题带注释Leetcode”是针对LeetCode平台的Java解题集合，特别适合初学者和希望巩固算法基础的开发者。LeetCode是一个流行的在线平台，提供了大量的编程题目，涵盖多种算法类型，旨在帮助程序员提高...
一个实用的java算法技术手册，适合各类JAVA开发人员参考和使用。
首先，让我们详细探讨一下Java算法的重要性。算法是解决问题的步骤或方法，是计算机科学的基础。在Java编程中，良好的算法设计和实现能力能够极大地提高代码的效率和可读性。通过解决这些算法题，开发者可以锻炼逻辑...
"JAVA算法应用"这一主题，涵盖了如何在Java程序中有效地实现和运用算法的知识点。 首先，我们要理解算法的基本概念。算法是一系列明确的指令，用于解决特定问题或执行特定任务。它们可以是简单的数据处理步骤，也...
基于AJAX的JAVA算法判断的正确于错误的分析基于AJAX的JAVA算法判断的正确于错误的分析基于AJAX的JAVA算法判断的正确于错误的分析基于AJAX的JAVA算法判断的正确于错误的分析基于AJAX的JAVA算法判断的正确于错误的分析
JAVA经典算法面试39题及答案 本资源总结了39道经典的 JAVA 算法面试题目，每个题目都附带答案，涵盖了常见的算法问题，旨在帮助读者更好地掌握 JAVA 编程语言和算法设计。 算法概述 算法是计算机科学中最重要的...
《Java算法导论》是一本深入探讨如何在Java编程环境中应用算法的重要著作。这本书的目标是帮助读者理解并掌握算法的设计、分析以及实现，通过使用Java编程语言，使学习过程更为直观和实用。以下是对该书内容的一些...