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");