Java中快速排序，冒泡排序和选择排序的实现

╰半夏微凉° 2022-06-10 13:27 190阅读 0赞

**一：快速排序的编程思想，写代码前的思考，这种排序方式比冒泡排序的时间复杂度要小很多**

分析如下：

5,6,8,7,2,9,1,3,4

i=0  
j=8  
4,6,8,7,2,9,1,3,5  
4,5,8,7,2,9,1,3,6  
4,3,8,7,2,9,1,5,6  
4,3,5,7,2,9,1,8,6  
4,3,1,7,2,9,5,8,6  
4,3,1,5,2,9,7,8,6  
4,3,1,2,5,9,7,8,6  
此时arr1<flag<arr2成立  
然后arr1和arr2再次进行上述操作  
数组长度为n  
设计一个套路，具体一步一步完成它  
1、设置两个变量i，j，在排序开始的时候i=0,j=n-1  
2、以数组的第一个元素，作为flag，flag=a\[0\]  
3、从j开始向前搜索，j--,找到第一个比flag小的，让a\[i\]和a\[j\]交换。  
4、从i开始向后搜索，i++，找到第一个比flag大的，让a\[i\]和a\[j\]交换。  
5、重复3~4的过程，知道i与j相遇为止。

6、把分裂开的arr1和arr2，都重复上述过程，知道全部都只剩1个元素为止。

用JavaScript实现上述：

document.write(arr);

下面是用Java代码实现：

package day04;  
  
  
public class Kssort \{  
  
  
/\*\*  
\* @param args  
\*/  
public static void main(String\[\] args) \{  
int\[\] arr = \{5,6,8,7,2,9,1,3,4\};  
fun(arr, 0, arr.length-1);  
for(int num:arr)\{  
System.out.print(num + " ");  
\}  
  
  
  
\}  
//start 和 end 是规定的两个标志位  
public static int\[\] fun(int\[\] arr,int start,int end)\{  
int n=start;  
int m = end;  
//开始按逻辑走，先从后往前遍历，载再从前往后遍历，start++，和end--，  
//知道start==end为止  
while(start != end)\{  
for(;start<end;end--)\{  
if(arr\[start\] > arr\[end\])\{  
int temp = arr\[start\];  
arr\[start\] = arr\[end\];  
arr\[end\] = temp;  
break;  
\}  
\}  
for(;start<end;start++)\{  
if(arr\[start\] > arr\[end\])\{  
int temp = arr\[start\];  
arr\[start\] = arr\[end\];  
arr\[end\] = temp;  
break;  
\}  
\}  
\}  
//进不去while循环，就说明start==end  此时数组被分为两部分  
if(start-1>n)\{  
fun(arr, n, start-1);  
\}  
if(end+1<m)\{  
fun(arr, end+1, m);  
\}  
return arr;  
\}  
  
  
\}

**二、冒泡排序：**

**![Center][]**

int\[\] arr = \{5,6,8,7,2,9,1,3,4\};

public static void main(String\[\] args) \{  
// TODO Auto-generated method stub  
int\[\] arr = \{5,6,8,7,2,9,1,3,4\};  
for(int i=0;i<arr.length-1;i++)\{  
for(int j=0; j< arr.length-1-i;j++)\{  
if(arr\[j\] > arr\[j+1\])\{  
int temp = arr\[j\];  
arr\[j\] =  arr\[j+1\];  
arr\[j+1\]  =temp;  
\}  
\}  
\}  
for(int num:arr)\{  
System.out.print(num+" ");  
\}

javascript实现如下：

**三、选择排序：**

![Center 1][]

用Java代码实现：

int\[\] arr = \{5,6,8,7,2,9,1,3,4\};  
for(int i=0; i< arr.length-1;i++)\{  
for(int j =i+1; j < arr.length; j++)\{  
if(arr\[i\] > arr\[j\])\{  
int temp = arr\[i\];  
arr\[i\] = arr\[j\];  
arr\[j\] = temp;  
\}  
\}  
\}  
for(int num:arr)\{  
System.out.print(num+" ");  
\}

用JavaScript实现：

[Center]: /images/20220610/12c1c545cd894c278dcf1a0964700cbe.png
[Center 1]: /images/20220610/1a60bd1c55284bbaa9aad35954049433.png