java排序算法(Java排序算法图解)

拼搏现实的明天。 2023-09-25 08:17 159阅读 0赞

## 如何理解排序算法的C++算法？ ##

排序算法C++算法编辑C++自带的algorithm库函数中提供了排序算法

![java排序算法(Java排序算法图解)\_java排序算法(Java排序算法图解)][java_Java_java_Java]

## 如何理解排序算法的C++算法？ ##

排序算法C++算法编辑C++自带的algorithm库函数中提供了排序算法 希望我的回答对你有用。

## java:设计一个通用的排序算法. ##

import java.util.Arrays;

class Stu implements Comparable\{

String name;

int id;

public Stu (String n, int i)\{

name = n;

id = i;

public int compareTo(Object o)\{

Stu m = (Stu) o;

if (id > m.id)\{

return 1;

\} else if(id < m.id)\{

return -1;

\} else return 0;

public String toString()\{

return "("+name+","+id+")";

class Rec implements Comparable\{

int c, k;

public Rec (int m, int n)\{

c = m;

k = n;

int area ()\{

return c\*k;

public int compareTo(Object o)\{

Rec m = (Rec) o;

if (this.area() > m.area())\{

return 1;

\} else if(this.area() < m.area()) \{

return -1;

\}else return 0;

public String toString()\{

return "(" + "边长为" + c + "和" + k + "面积为" + this.area() + ")";

public class TestSort \{

public static void main (String \[\] args)\{

Stu \[\] a = new Stu \[5\];

a\[0\] = new Stu("ZhangSan",6);

a\[1\] = new Stu("LiSi",3);

a\[2\] = new Stu("WangWu",9);

a\[3\] = new Stu("ZhaoLiu",12);

a\[4\] = new Stu("QianQi",4);

sort (a);

for (int i=0; i1; i--)\{

for(int j=0; j1)\{

Comparable c =(Comparable) o\[j\];

o\[j\] = o\[j+1\];

o\[j+1\] = c;

\}\*/

\}import java.util.arrays;

class stu implements comparable\{

string name;

int id;

public stu (string n, int i)\{

name = n;

id = i;

public int compareto(object o)\{

stu m = (stu) o;

if (id > m.id)\{

return 1;

\} else if(id < m.id)\{

return -1;

\} else return 0;

public string tostring()\{

return "("+name+","+id+")";

class rec implements comparable\{

int c, k;

public rec (int m, int n)\{

c = m;

k = n;

int area ()\{

return c\*k;

public int compareto(object o)\{

rec m = (rec) o;

if (this.area() > m.area())\{

return 1;

\} else if(this.area() < m.area()) \{

return -1;

\}else return 0;

public string tostring()\{

return "(" + "边长为" + c + "和" + k + "面积为" + this.area() + ")";

public class testsort \{

public static void main (string \[\] args)\{

stu \[\] a = new stu \[5\];

a\[0\] = new stu("zhangsan",6);

a\[1\] = new stu("lisi",3);

a\[2\] = new stu("wangwu",9);

a\[3\] = new stu("zhaoliu",12);

a\[4\] = new stu("qianqi",4);

sort (a);

for (int i=0; i

system.out.println("name="+ a\[i\].name + " " + "id=" + a\[i\].id);

rec\[\] b = \{new rec(4,5), new rec(7,2), new rec(8,3), new rec(2,11), new rec(5,5)\};

system.out.println();

arrays.sort(a); //此为调用arrays.sort()方法自动排序;

system.out.println("排序后"+arrays.tostring(a));

arrays.sort(b);

system.out.println("排序后"+arrays.tostring(b));

/\*下面为用冒泡排序法排序;本人学艺不精，有一点小问题，编译时可以通过，但是不起作用。主要是定义comparable对象c来传递o对象的值时出现传递不成功的现象。

static void sort (comparable\[\] o)\{

int m = o.length-1;

for(int i=m; i>1; i--)\{

for(int j=0; j

if(o\[j\].compareto(o\[j+1\])>1)\{

comparable c =(comparable) o\[j\];

o\[j\] = o\[j+1\];

o\[j+1\] = c;

\}\*/

![java排序算法(Java排序算法图解)\_java排序算法(Java排序算法图解)\_02][java_Java_java_Java_02]

## JAVA中有哪几种常用的排序方法？每个排序方法的实现思路是如何的？每个方法的思想是什么？？ ##

一、冒泡排序

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先比较 a\[1\]与a\[2\]的值，若a\[1\]大于a\[2\]则交换两者的值，否则不变。再比较a\[2\]与a\[3\]的值，若a\[2\]大于a\[3\]则交换两者的值，否则不变。再比较a\[3\]与a\[4\]，以此类推，最后比较a\[n-1\]与a\[n\]的值。这样处理一轮后，a\[n\]的值一定是这组数据中最大的。再对 a\[1\]~a\[n-1\]以相同方法处理一轮，则a\[n-1\]的值一定是a\[1\]~a\[n-1\]中最大的。再对a\[1\]~a\[n-2\]以相同方法处理一轮，以此类推。共处理n-1轮后a\[1\]、a\[2\]、……a\[n\]就以升序排列了。

优点：稳定；

缺点：慢，每次只能移动相邻两个数据。

二、选择排序

冒泡排序的改进版。

每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R\[1..n\]，有序区为空。

②第1趟排序

在无序区R\[1..n\]中选出关键字最小的记录R\[k\]，将它与无序区的第1个记录R\[1\]交换，使R\[1..1\]和R\[2..n\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R\[1..i-1\]和R(1≤i≤n- 1)。该趟排序从当前无序区中选出关键字最小的记录 R\[k\]，将它与无序区的第1个记录R交换，使R\[1..i\]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点：移动数据的次数已知(n-1次)；

缺点：比较次数多。

三、插入排序

已知一组升序排列数据a\[1\]、a\[2\]、……a\[n\]，一组无序数据b\[1\]、 b\[2\]、……b\[m\]，需将二者合并成一个升序数列。首先比较b\[1\]与a\[1\]的值，若b\[1\]大于a\[1\]，则跳过，比较b\[1\]与a\[2\]的值，若b\[1\]仍然大于a\[2\]，则继续跳过，直到b\[1\]小于a数组中某一数据a\[x\]，则将a\[x\]~a\[n\]分别向后移动一位，将b\[1\]插入到原来 a\[x\]的位置这就完成了b\[1\]的插入。b\[2\]~b\[m\]用相同方法插入。(若无数组a，可将b\[1\]当作n=1的数组a)

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

三、缩小增量排序

由希尔在1959年提出，又称希尔排序(shell排序)。

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

四、快速排序

快速排序是目前已知的最快的排序方法。

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先任取数据 a\[x\]作为基准。比较a\[x\]与其它数据并排序，使a\[x\]排在数据的第k位，并且使a\[1\]~a\[k-1\]中的每一个数据a\[x\]，然后采用分治的策略分别对a\[1\]~a\[k-1\]和a\[k+1\]~a\[n\] 两组数据进行快速排序。

优点：极快，数据移动少；

缺点：不稳定。

五、箱排序

已知一组无序正整数数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先定义一个数组x\[m\],且m>=a\[1\]、a\[2\]、……a\[n\]，接着循环n次，每次x\[a\]++.

优点：快，效率达到O(1)

缺点：数据范围必须为正整数并且比较小

六、归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.最主要的是冒泡排序、选择排序、插入排序以及快速排序

1、冒泡排序

冒泡排序是一个比较简单的排序方法。在待排序的数列基本有序的情况下排序速度较快。若要排序的数有n个，则需要n-1轮排序，第j轮排序中，从第一个数开始，相邻两数比较，若不符合所要求的顺序，则交换两者的位置；直到第n+1-j个数为止，第一个数与第二个数比较，第二个数与第三个数比较，......，第n-j个与第n+1-j个比较，共比较n-1次。此时第n+1-j个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。

例如：第一轮排序：第一个数与第二个数进行比较，若不符合要求的顺序，则交换两者的位置，否则继续进行二个数与第三个数比较......。直到完成第n-1个数与第n个数的比较。此时第n个位置上的数已经按要求排好，它不参与以后的比较和交换操作；第二轮排序：第一个数与第二个数进行比较，......直到完成第n-2个数与第n-1个数的比较；......第n-1轮排序：第一个数与第二个数进行比较，若符合所要求的顺序，则结束冒泡法排序；若不符合要求的顺序，则交换两者的位置，然后结束冒泡法排序。

共n-1轮排序处理，第j轮进行n-j次比较和至多n-j次交换。

从以上排序过程可以看出，较大的数像气泡一样向上冒，而较小的数往下沉，故称冒泡法。

public void bubbleSort(int a\[\])

int n = a.length;

for(int i=0;i

for(int j=0;j

if(a\[j\] > a\[j+1\])

int temp = a\[j\];

a\[j\] = a\[j + 1\];

a\[j + 1\] = temp;

2、选择排序

选择法的原理是先将第一个数与后面的每一个数依次比较,不断将将小的赋给第一个数,从而找出最小的,然后第二个数与后面的每一个数依次比较,从而找出第二小的,然后第三个数与后面的每一个数依次比较,从而找出第三小的.....直到找到最后一个数。

public void sort(int x\[\])

int n=x.length;

int k,t;

for(int i=0;i

for(int j=i+1;j=n;j++)

if(x\[j\]>x\[k\])k=j;

if(k!=i)

t=x\[i\];

x\[i\]=x\[k\];

x\[k\]=t;

3、插入排序

插入排序的原理是对数组中的第i个元素，认为它前面的i-1个已经排序好，然后将它插入到前面的i-1个元素中。插入排序对少量元素的排序较为有效.

public void sort(int obj\[\])

for(int j=1;j

int key=obj\[j\];

int i=j-1;

while(i>=0&&obj\[i\]>key)

obj\[i+1\]=obj\[i\];

obj\[i+1\]=key;

4、快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此大道整个数据变成有序序列。

public void quickSort(int obj\[\],int low,int high)

int i=low;

int j=high;

int keyValue=obj\[i\];

while(i

int temp=0;

while(i =keyValue)

j=j-1;

temp=obj\[j\];

obj\[j\]=obj\[i\];

obj\[i\]=temp;

while(i

i=i+1;

temp=obj\[j\];

obj\[j\]=ojb\[i\];

obj\[i\]=temp;

obj\[i\]=keyValue;

if(low

quickSort(obj,low,i-1);

if(high>i+1)

quickSort(obj,i+1,high);

\}如果说是Java中，常用的就一种：Collections.sort。思路就是：使用系统自带的排序，排序的每个元素实现Comparable接口。

如果说，算法上有哪几种常用的排序方法，那是一个和Java本身完全无关的问题，你用C++实现也一样的。然而如果你用C++，它也有它自带的排序，同样是系统函数。

所以当你要排序，用系统自带函数就行了。Java系统还可能实现底层优化，是你自己写排序函数做不到的。

想知道算法上的排序方法，这里给你算法的名字：

基础的慢速的：bubblesort,insertsort复杂度nlogn

常用的：quicksort,mergesort,heapsort复杂度nlogn

最牛的却不总是能用的：shellsort(又叫bucketsort,radixsort)复杂度n冒泡排序：

a.比较相邻的元素。如果第一个比第二个大，就交换他们两个

b.>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数

c.针对所有的元素重复以上的步骤，除了最后一个

d.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

a.从数列中挑出一个元素，称为“基准

b.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后，

\* 该基准是它的最后位置。这个称为分割(partition)操作。

c.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

a. 在未排序序列中找到最小元素，存放到排序序列的起始位置

b.再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾

c.以此类推，直到所有元素均排序完毕

a.从第一个元素开始，该元素可以认为已经被排序

b.取出下一个元素，在已经排序的元素序列中从后向前扫描

c.如果该元素(已排序)大于新元素，将该元素移到下一位置

d.重复步骤c，直到找到已排序的元素小于或者等于新元素的位置

e.将新元素插入到该位置中

a.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

b.设定两个指针，最初位置分别为两个已经排序序列的起始位置

c.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

d.重复步骤c直到某一指针达到序列尾

e.将另一序列剩下的所有元素直接复制到合并序列尾直接插入:将n个元素看成一个有序表和n个无序表(这样循环执行,就可实现)

折半插入排序:将n个元素将其折半，递归条件下，将单元的元素序列排序，最终将各子序列排序

希尔排序:又称"缩小增量排序",将相隔单元增量的两个元素比较，据大小互相调换位置

选择排序:将第一个元素与其下的所有元素比较，据大小相互调换位置,如此循环

堆排序:将n个元素看成一棵二叉树,一层一层的子节点与父节点相互间比较,如此据大小调换位置

冒泡排序:从n个元素从最后一个元素，与其上一个元素一个一个的比较，据大小调换位置

快速排序:"划分交换排序",用一个基准，(自左向右或自右向左)将其他的元素与其比较，且交换位置

归并排序:将已排序好的子序列合并成一个整体的序列

这是我自己的一些见解，可能不是很全面，但大致的意思也差不多，希望对您有帮助，加油啊！！

[java_Java_java_Java]: https://img2.baidu.com/it/u=1163517272,2784615593&fm=26&fmt=auto
[java_Java_java_Java_02]: https://img2.baidu.com/it/u=1509598574,2824804256&fm=26&fmt=auto