package person.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
/**
* class name: RapidSort
* description: Java快速排序法：数组和集合
* @author Jr
*
*/
public class RapidSort {
private Random ran = new Random(); // 声明一个全局变量ran，用来随机生成整数
/**
* method name: sortArray
* description: 对数组的快速排序，只能用于int[]类型的数组
* @return
*/
private void sortArray() {
int[] array = new int[10]; // 声明数组长度为10
for (int i = 0 ; i < array.length; i++) {
array[i] = ran.nextInt(10) + 1; // 数组赋值
}
Arrays.sort(array);
System.out.println(Arrays.toString(array));
}
/**
* method name: sortList
* description: 对集合的快速排序，可以用于List<Object>类型数组，
* 隐含意思就是对所有类型数组都适用
* @return
*/
private void sortList() {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0 ; i < 10; i++) {
list.add(ran.nextInt(10) + 1); // 给集合赋10个值
}
Collections.sort(list);
System.out.println(list);
}
public static void main(String[] args) {
RapidSort rs = new RapidSort();
rs.sortArray();
rs.sortList();
}
}
㈡ 怎么用java实现快速排序
package com.xinhua.test2;
public class Student {
int sno;
String name;
double chiness;
double math;
double english;
double three_sco;
double all_s;
public Student(int sno, String name, double chiness, double math, double english, double three_sco) {
this.sno = sno;
this.name = name;
this.chiness = chiness;
this.math = math;
this.english = english;
this.three_sco = three_sco;
}
@Override
public String toString() {
return "学号：" + sno + ", 名字：" + name + ", 语文成绩：" + chiness + ", 数学成绩：" + math + ", 英语成绩："
+ english + "总成绩："+(chiness+math+english+three_sco);
}
public static void main(String[] args) {
Student A=new Student(1, "张三", 118, 145, 114.5, 198);
Student B=new Student(2, "李四", 130,110.5,100,210);
Student C=new Student(3, "王五",142.5,120,87.5,245.5);
System.out.println("学生列表信息为：");
System.out.println(A.toString());
System.out.println(B.toString());
System.out.println(C.toString());
//
double a_scoAll=A.chiness+A.math+A.english+A.three_sco;
A.all_s=a_scoAll;
double b_scoAll=B.chiness+B.math+B.english+B.three_sco;
B.all_s=b_scoAll;
double c_sclAll=C.chiness+C.math+C.english+C.three_sco;
C.all_s=c_sclAll;
Student[] s_s={A,B,C};
System.out.println("按总成绩从大到小排序为");
Student temp;
for(int i=0;i<s_s.length;i++){
for(int j=1;j<s_s.length-i;j++){
if(s_s[j-1].all_s < s_s[j].all_s){
temp=s_s[j-1] ;
s_s[j-1] =s_s[j];
s_s[j]=temp;
}
}
}
for(int i=0;i<s_s.length;i++){
System.out.println("第"+(i+1)+"名为："+s_s[i].toString());
}
}
}
㈢ java中快速排序的实现思路
快速排序法：快速排序法号称是目前最优秀的算法之一，实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2
㈣ Java快速排序
原理：
快速排序也是分治法思想的一种实现，他的思路是使数组中的每个元素与基准值（Pivot，通常是数组的首个值，A[0]）比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程：选基准值，小的放在左边，大的放在右边。。。直到排序结束。
步骤：
1.找基准值，设Pivot = a[0]
2.分区（Partition）：比基准值小的放左边，大的放右边，基准值(Pivot)放左部与右部的之间。
3.进行左部（a[0] - a[pivot-1]）的递归，以及右部（a[pivot+1] - a[n-1]）的递归，重复上述步骤
㈤ java快速排序问题
帮你改了一下：
public class Point{
public static void main(String[] args) {
int[] a = {4,63,2,4,4,6,43,2,3};
quickSort(a, 0, a.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ",");
}
}
static int Partition(int[] a, int left, int right)
{
int tmp;
//进行一趟快速排序,返回中心记录位置
int pivot = a[left];//把中心置于a[0]
while (left < right)
{
while(left<right && a[right]>=pivot)
right--;
//将比中心记录小的移到低端
tmp = a[right];
a[right] = a[left];
a[left] = tmp;
while(left<right && a[left]<=pivot)
left++;
tmp = a[right];
a[right] = a[left];
a[left] = tmp;
//将比中心记录大的移到高端
}
a[left] = pivot; //中心移到正确位置
return left; //返回中心位置
}
public static void quickSort(int[] a, int left, int right) {
if(left >= right - 1)
return;
int pivot = Partition(a,left,right);
quickSort(a, left, pivot-1);
quickSort(a, pivot+1, right);
}
}
㈥ java十大算法
算法一：快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1 从数列中挑出一个元素，称为 "基准"（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法二：堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1
算法三：归并排序
归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素
㈦ java快速排序 要求0-100之间随机的20个数 并存放在list里。
importjava.util.ArrayList;
importjava.util.List;
publicclassCat
{
/**
*快速排序
*/
privatestaticvoidquickSort(List<Integer>array,intstart,intend)
{
if(start<end)
{
intkey=array.get(start);
inti=start;
for(intj=start+1;j<end+1;j++)
{
if(key>array.get(j))
{
inttemp=array.get(j);
array.set(j,array.get(i+1));
array.set(i+1,temp);
i++;
}
}
array.set(start,array.get(i));
array.set(i,key);
quickSort(array,start,i-1);
quickSort(array,i+1,end);
}
}
publicstaticvoidmain(String[]args)
{
List<Integer>array=newArrayList<Integer>();
for(inti=0;i<20;i++)
{
intrand=(int)(Math.random()*100);
array.add(rand);
}
System.out.println(array);
quickSort(array,0,array.size()-1);
System.out.println(array);
}
}
㈧ 用JAVA实现快速排序算法
public void quickSort(int left,int right,int a[])
{
int l=left;
int r=right;
int pivot=a[(l+r)/2];//转轴数
int temp=0;
while(l<r)
{
while(a[l]<pivot)l++;
while(a[r]>pivot)r--;
if(l>=r)break;
temp=a[l];
a[l]=a[r];
a[r]=temp;
if(a[l]==pivot)r--;
if(a[r]==pivot)l++;
}
if(l==r)
{
l++;
r--;
}
if(left<r)quickSort(left,r,a);
if(right>l)quickSort(l,right,a);
}
㈨ 请给出java几种排序方法
java常见的排序分为：
1 插入类排序
主要就是对于一个已经有序的序列中，插入一个新的记录。它包括：直接插入排序，折半插入排序和希尔排序
2 交换类排序
这类排序的核心就是每次比较都要“交换”，在每一趟排序都会两两发生一系列的“交换”排序，但是每一趟排序都会让一个记录排序到它的最终位置上。它包括：起泡排序，快速排序
3 选择类排序
每一趟排序都从一系列数据中选择一个最大或最小的记录，将它放置到第一个或最后一个为位置交换，只有在选择后才交换，比起交换类排序，减少了交换记录的时间。属于它的排序：简单选择排序，堆排序
4 归并类排序
将两个或两个以上的有序序列合并成一个新的序列
5 基数排序
主要基于多个关键字排序的。
下面针对上面所述的算法，讲解一些常用的java代码写的算法
二 插入类排序之直接插入排序
直接插入排序,一般对于已经有序的队列排序效果好。
基本思想：每趟将一个待排序的关键字按照大小插入到已经排序好的位置上。
算法思路，从后往前先找到要插入的位置，如果小于则就交换，将元素向后移动，将要插入数据插入该位置即可。时间复杂度为O(n2),空间复杂度为O(1)
package sort.algorithm;
public class DirectInsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
int temp, j;
for (int i = 1; i < data.length; i++) {
temp = data[i];
j = i - 1;
// 每次比较都是对于已经有序的
while (j >= 0 && data[j] > temp) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
// 输出排序好的数据
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
三 插入类排序之折半插入排序(二分法排序)
条件：在一个已经有序的队列中，插入一个新的元素
折半插入排序记录的比较次数与初始序列无关
思想：折半插入就是首先将队列中取最小位置low和最大位置high，然后算出中间位置mid
将中间位置mid与待插入的数据data进行比较，
如果mid大于data，则就表示插入的数据在mid的左边，high=mid-1;
如果mid小于data，则就表示插入的数据在mid的右边,low=mid+1
最后整体进行右移操作。
时间复杂度O(n2),空间复杂度O(1)
package sort.algorithm;
//折半插入排序
public class HalfInsertSort {
public static void main(String[] args) {
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
// 存放临时要插入的元素数据
int temp;
int low, mid, high;
for (int i = 1; i < data.length; i++) {
temp = data[i];
// 在待插入排序的序号之前进行折半插入
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < data[mid])
high = mid - 1;
else
// low=high的时候也就是找到了要插入的位置，
// 此时进入循环中，将low加1，则就是要插入的位置了
low = mid + 1;
}
// 找到了要插入的位置，从该位置一直到插入数据的位置之间数据向后移动
for (int j = i; j >= low + 1; j--)
data[j] = data[j - 1];
// low已经代表了要插入的位置了
data[low] = temp;
}
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
四 插入类排序之希尔排序
希尔排序，也叫缩小增量排序，目的就是尽可能的减少交换次数，每一个组内最后都是有序的。
将待续按照某一种规则分为几个子序列，不断缩小规则，最后用一个直接插入排序合成
空间复杂度为O(1)，时间复杂度为O(nlog2n)
算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
package sort.algorithm;
public class ShellSort {
public static void main(String[] args) {
int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };
double d1 = a.length;
int temp = 0;
while (true)
{
//利用这个在将组内倍数减小
//这里依次为5,3,2,1
d1 = Math.ceil(d1 / 2);
//d为增量每个分组之间索引的增量
int d = (int) d1;
//每个分组内部排序
for (int x = 0; x < d; x++)
{
//组内利用直接插入排序
for (int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >= 0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d == 1)
break;
}
for (int i = 0; i < a.length; i++)
System.out.print(a[i]+" ");
}
}
五 交换类排序之冒泡排序
交换类排序核心就是每次比较都要进行交换
冒泡排序：是一种交换排序
每一趟比较相邻的元素，较若大小不同则就会发生交换，每一趟排序都能将一个元素放到它最终的位置！每一趟就进行比较。
时间复杂度O(n2)，空间复杂度O(1)
package sort.algorithm;
//冒泡排序：是一种交换排序
public class BubbleSort {
// 按照递增顺序排序
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20, 13, 100, 37, 16 };
int temp = 0;
// 排序的比较趟数,每一趟都会将剩余最大数放在最后面
for (int i = 0; i < data.length - 1; i++) {
// 每一趟从开始进行比较，将该元素与其余的元素进行比较
for (int j = 0; j < data.length - 1; j++) {
if (data[j] > data[j + 1]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}
㈩ 排序都有哪几种方法用JAVA实现一个快速排序。
前置 后置 冒泡
int mp[] = new int[1,2,12,22,58,48,0];
for (int i = 0; i < mp.length; i++) {
for (int j = 0; j < mp.length; j++) {
int temp;
if (mp[i] < mp[j]) {
temp = mp[j];
mp[j] = mp[i];
mp[i] = temp;
}
}
}
for (int i = 0; i < mp.length; i++) {
System.out.print(mp[i] + " ");
}
System.out.print("\n");