189 8069 5689

直接排序java代码 java直接排序算法

java快速排序简单代码

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法:

目前成都创新互联已为近千家的企业提供了网站建设、域名、虚拟空间、网站托管、服务器租用、企业网站设计、银州网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是 O(n?),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

1. 算法步骤

从数列中挑出一个元素,称为 "基准"(pivot);

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

2. 动图演示

代码实现 JavaScript 实例 function quickSort ( arr , left , right ) {

var len = arr. length ,

    partitionIndex ,

    left = typeof left != 'number' ? 0 : left ,

    right = typeof right != 'number' ? len - 1 : right ;

if ( left

求java快速排序的正确代码

一趟快速怕序的具体做法是:附设两个指针low和high,他们的初值分别为low和high,设枢轴记录的关键字为privotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指向的位置起向后搜索,找到第一个关键字大于privotkey的记录和枢轴记录互相交换,重复这两步直至low==high位置.

import java.util.concurrent.Executor;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;

public class 快速排序_1 {

public static void main(String[] args) throws InterruptedException {

int test[] = {15,23,56,7,13,52,20,7};

new 快速排序_1().qSort(test, 0, test.length-1);

for(int k:test) System.out.println(k);

}

public void qSort(int []array,int low,int high){

if(low

int privot=partition(array,low,high);

qSort(array,low,privot-1);

qSort(array,privot+1,high);

}

}

public int partition(int [] array,int low,int high){

/**

* 选择 low位置 作为曲轴(支点)

*/

int pivot=array[low];

int temp=0;

/**

* 如果 low

*/

while(low

/**

* 先从 high端 开始判断

*/

while(low=pivot) high--;

/**

* 进行 置换操作

*/

if(low

array[low]=array[high];

low++;

}

/**

* 从 low 端判断

*/

while(low

/**

* 进行 置换操作

*/

if(low

array[high]=array[low];

high--;

}

}

array[low]=pivot;

return low;

}

}

java中排序算法代码

package temp;

import sun.misc.Sort;

/**

* @author zengjl

* @version 1.0

* @since 2007-08-22

* @Des java几种基本排序方法

*/

/**

* SortUtil:排序方法

* 关于对排序方法的选择:这告诉我们,什么时候用什么排序最好。当人们渴望先知道排在前面的是谁时,

* 我们用选择排序;当我们不断拿到新的数并想保持已有的数始终有序时,我们用插入排序;当给出的数

* 列已经比较有序,只需要小幅度的调整一下时,我们用冒泡排序。

*/

public class SortUtil extends Sort {

/**

* 插入排序法

* @param data

* @Des 插入排序(Insertion Sort)是,每次从数列中取一个还没有取出过的数,并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。

*/

public int[] insertSort(int[] data) {

1/11页

int temp;

for (int i = 1; i data.length; i++) {

for (int j = i; (j 0) (data[j] data[j - 1]); j--) {

swap(data, j, j - 1);

}

}

return data;

}

/**

* 冒泡排序法

* @param data

* @return

* @Des 冒泡排序(Bubble Sort)分为若干趟进行,每一趟排序从前往后比较每两个相邻的元素的大小(因此一趟排序要比较n-1对位置相邻的数)并在

* 每次发现前面的那个数比紧接它后的数大时交换位置;进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作(最坏情况下要跑n-1趟,

* 这种情况在最小的数位于给定数列的最后面时发生)。事实上,在第一趟冒泡结束后,最后面那个数肯定是最大的了,于是第二次只需要对前面n-1

* 个数排序,这又将把这n-1个数中最小的数放到整个数列的倒数第二个位置。这样下去,冒泡排序第i趟结束后后面i个数都已经到位了,第i+1趟实

* 际上只考虑前n-i个数(需要的比较次数比前面所说的n-1要小)。这相当于用数学归纳法证明了冒泡排序的正确性

直接选择排序Java实现

About this application:

This application implements Straight Selection Sort algorithm which is described like this:

If there are N numbers find the minimum and exchange it with the first number then N numbers remained Continue to find the minimum number in the remained N numbers and exchange it with the second number Repeat this until all the numbers are in order

Note: This is SWT application so you need eclipse swt win win x _ v b jar eclipse jface_ I jar mands_ I jar This is for Eclipse

Source Code:

package selection sort;

import java util ArrayList;

import eclipse swt SWT;

import eclipse swt events KeyAdapter;

import eclipse swt events KeyEvent;

import eclipse swt events ModifyEvent;

import eclipse swt events ModifyListener;

import eclipse swt events SelectionAdapter;

import eclipse swt events SelectionEvent;

import eclipse swt layout FormAttachment;

import eclipse swt layout FormData;

import eclipse swt layout FormLayout;

import eclipse swt widgets Button;

import eclipse swt widgets Display;

import eclipse swt widgets Group;

import eclipse swt widgets Label;

import eclipse swt widgets Shell;

import eclipse swt widgets Text;

/**

* This application implements Straight Selection Sort algorithm which means

* get the minimum number from the numbers and exchange it with the first

* number then doing this for other numbers except the first number Repeat

* this until all numbers are in order If you have any suggestion or problem

* please e mail to

*

* @author vivien Data:

*/

public class StraightSelectionSort {

/** The string containing the number wait for sorted */

public String numString = new String();

public Text numText;

public Text resText;

public Button btSort;

public Label errorLabel;

/** The flag to indicate if there is any error for inputed numbers */

public boolean hasError = false;

/** The arrayList containing the double numbers wait for sorted */

public ArrayListDouble numList = new ArrayListDouble();

public static void main(String[] args) {

StraightSelectionSort selectionSort = new StraightSelectionSort();

selectionSort createControl();

}

/**

* Create the control for the interface

*/

public void createControl() {

Display display = new Display();

Shell shell = new Shell(display);

shell setBounds( );

// Set Title

shell setText( Straight selection sort );

FormLayout layout = new FormLayout();

shell setLayout(layout);

FormData fd = new FormData();

// The Start Sort button

btSort = new Button(shell SWT NONE | SWT CENTER);

btSort setText( Start Sort );

fd = new FormData();

fd height = ;

fd top = new FormAttachment( );

fd left = new FormAttachment( );

btSort setLayoutData(fd);

// The Input numbers group

Group numGroup = new Group(shell SWT NONE);

numGroup setText( Input numbers: );

numGroup setLayout(layout);

fd = new FormData();

fd top = new FormAttachment( );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

fd bottom = new FormAttachment(btSort );

numGroup setLayoutData(fd);

// Label for input numbers

Label numLabel = new Label(numGroup SWT WRAP);

numLabel

setText( Please input the numbers you want to sort: (Note: Numbers need to be seperated by space) );

fd = new FormData();

fd top = new FormAttachment( );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

numLabel setLayoutData(fd);

// Text for input numbers

numText = new Text(numGroup SWT BORDER | SWT MULTI | SWT V_SCROLL

| SWT WRAP);

numText setToolTipText( Numbers need to be seperated by space );

fd = new FormData();

fd top = new FormAttachment(numLabel );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

fd bottom = new FormAttachment( );

numText setLayoutData(fd);

// The results group

Group resGroup = new Group(shell SWT NONE);

resGroup setText( The results: );

resGroup setLayout(layout);

fd = new FormData();

fd top = new FormAttachment(btSort );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

fd bottom = new FormAttachment( );

resGroup setLayoutData(fd);

// Label for results

Label resLabel = new Label(resGroup SWT WRAP);

resLabel

setText( The results after sorted are: (Note: Results are seperated by space) );

fd = new FormData();

fd top = new FormAttachment( );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

resLabel setLayoutData(fd);

// Text for results

resText = new Text(resGroup SWT BORDER | SWT MULTI | SWT V_SCROLL

| SWT WRAP);

resText setToolTipText( Results are seperated by space );

resText setEditable(false);

fd = new FormData();

fd top = new FormAttachment(resLabel );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

fd bottom = new FormAttachment( );

resText setLayoutData(fd);

// Label for showing error message

errorLabel = new Label(shell SWT NONE);

fd = new FormData();

fd top = new FormAttachment( );

fd left = new FormAttachment( );

fd right = new FormAttachment( );

fd bottom = new FormAttachment( );

errorLabel setLayoutData(fd);

errorLabel setForeground(display getSystemColor(SWT COLOR_RED));

// Listen to the numText change

numText addModifyListener(new ModifyListener() {

@Override

public void modifyText(ModifyEvent e) {

numString = numText getText() trim();

hasError = false;

}

});

// If press Return focus go to Start Sort button and start sort

numText addKeyListener(new KeyAdapter() {

@Override

public void keyPressed(KeyEvent e) {

if (e keyCode == \r ) {

e doit = false;

btSort setFocus();

startSort();

}

}

});

// Listen to the button selection

btSort addSelectionListener(new SelectionAdapter() {

public void widgetSelected(SelectionEvent e) {

startSort();

}

});

shell open();

while (!shell isDisposed()) {

if (!display readAndDispatch())

display sleep();

}

display dispose();

}

/**

* Get double values from string

*/

public void getDoubleFromString() {

int index = ;

// Split string using space

String[] splitedNumbers = numString split( );

if (numList size() != )

// Clear the arrayList for last used

numList clear();

for (int i = ; i splitedNumbers length; i++) {

if (splitedNumbers[i] trim() length() != ) {

try {

numList add(index++ Double valueOf(splitedNumbers[i]));

} catch (NumberFormatException e) {

setErrorMessage( Please input the correct numbers );

hasError = true;

break;

}

}

}

}

/**

* Start sort the string containing numbers waited for sort

*/

public void startSort() {

if (numString != null)

if (numString trim() length() != ) {

getDoubleFromString();

startStraightSelectionSort();

setResults();

} else {

setErrorMessage( Please input numbers );

hasError = true;

}

}

/**

* Set the results to the results group

*/

public void setResults() {

if (!hasError) {

String resString = new String();

for (int i = ; i numList size(); i++)

if (i != numList size() )

resString = resString + numList get(i) + ;

else

// If be the last string

resString = resString + numList get(i);

resText setText(resString);

// Clear errorLabel

errorLabel setText( );

}

}

/**

* Sort the numbers using Straight selection Sort algorithm

*/

public void startStraightSelectionSort() {

int minPosition = ;

for (int j = ; j numList size() ; j++) {

minPosition = j;

for (int i = j + ; i numList size(); i++) {

if (numList get(i) numList get(minPosition)) {

minPosition = i;

}

}

if (minPosition != j) {

// Exchange the minimum with the first number of the numbers

// waited for sort

double temp = numList get(j);

numList set(j numList get(minPosition));

numList set(minPosition temp);

}

}

}

/**

* Set the error message on the error Label

*

* @param errorString

*            The string used for set on the errorLabel

*/

public void setErrorMessage(String errorString) {

errorLabel setText(errorString);

// Clear the text of results

resText setText( );

hasError = true;

}

}

Black box Test Case:

)      All numbers are zero:


本文标题:直接排序java代码 java直接排序算法
本文URL:http://cdxtjz.cn/article/dosiicg.html

其他资讯