数组快速排序

墨蓝 2022-03-20 04:28 215阅读 0赞

## **[常用数组排序算法][Link 1]** ##

1.    
2.    
3.  **public** **class** SortAll \{  
4.    
5.   /\*\* 
6.    \* 冒泡排序，选择排序，插入排序，希尔（Shell），快速排序 排序 Java的实现  
7.    \* 2009.6.4 
8.    \* @千醉. （http://b1135519.xici.net) 
9.    \*/  
10.  **public** **static** **void** main(String\[\] args) \{  
11.   **int**\[\] i = \{ 1, 5, 6, 12, 4, 9, 3, 23, 39, 403, 596, 87 \};  
12.   System.out.println("----冒泡排序的结果：");  
13.   maoPao(i);  
14.   System.out.println();  
15.   System.out.println("----选择排序的结果：");  
16.   xuanZe(i);  
17.   System.out.println();  
18.   System.out.println("----插入排序的结果：");  
19.   chaRu(i);  
20.   System.out.println();  
21.   System.out.println("----希尔（Shell）排序的结果：");  
22.   shell(i);  
23.  \}  
24. </span>

## ** // 冒泡排序** ##

1.  **public** **static** **void** maoPao(**int**\[\] x) \{  
2.    **for** (**int** i = 0; i < x.length; i++) \{  
3.     **for** (**int** j = i + 1; j < x.length; j++) \{  
4.      **if** (x\[i\] > x\[j\]) \{  
5.       **int** temp = x\[i\];  
6.       x\[i\] = x\[j\];  
7.       x\[j\] = temp;  
8.      \}  
9.     \}  
10.   \}  
11.   **for** (**int** i : x) \{  
12.    System.out.print(i + " ");  
13.   \}  
14.  \}

## ** // 选择排序** ##

1.  **public** **static** **void** xuanZe(**int**\[\] x) \{  
2.    **for** (**int** i = 0; i < x.length; i++) \{  
3.     **int** lowerIndex = i;  
4.     // 找出最小的一个索引  
5.     **for** (**int** j = i + 1; j < x.length; j++) \{  
6.      **if** (x\[j\] < x\[lowerIndex\]) \{  
7.       lowerIndex = j;  
8.      \}  
9.     \}  
10.    // 交换  
11.    **int** temp = x\[i\];  
12.    x\[i\] = x\[lowerIndex\];  
13.    x\[lowerIndex\] = temp;  
14.   \}  
15.   **for** (**int** i : x) \{  
16.    System.out.print(i + " ");  
17.   \}  
18.  \}  
19.   
20.  // 插入排序  
21.  **public** **static** **void** chaRu(**int**\[\] x) \{  
22.   **for** (**int** i = 1; i < x.length; i++) \{ // i从一开始，因为第一个数已经是排好序的啦  
23.    **for** (**int** j = i; j > 0; j--) \{  
24.     **if** (x\[j\] < x\[j - 1\]) \{  
25.      **int** temp = x\[j\];  
26.      x\[j\] = x\[j - 1\];  
27.      x\[j - 1\] = temp;  
28.     \}  
29.    \}  
30.   \}  
31.   **for** (**int** i : x) \{  
32.    System.out.print(i + " ");  
33.   \}  
34.  \}

## ** // 希尔排序** ##

1.  **public** **static** **void** shell(**int**\[\] x) \{  
2.    // 分组  
3.    **for** (**int** increment = x.length / 2; increment > 0; increment /= 2) \{  
4.     // 每个组内排序  
5.     **for** (**int** i = increment; i < x.length; i++) \{  
6.      **int** temp = x\[i\];  
7.      **int** j = 0;  
8.      **for** (j = i; j >= increment; j -= increment) \{  
9.       **if** (temp < x\[j - increment\]) \{  
10.       x\[j\] = x\[j - increment\];  
11.      \} **else** \{  
12.       **break**;  
13.      \}  
14.     \}  
15.     x\[j\] = temp;  
16.    \}  
17.   \}  
18.   
19.   **for** (**int** i : x) \{  
20.    System.out.print(i + " ");  
21.   \}  
22.  \}  
23. \}

## **//快速排序** ##

1.  /\*\* 快速排序方法 \*/  
2.      **public** **static** **void** quickSort(**int**\[\] a, **int** lo0, **int** hi0) \{  
3.          **int** lo = lo0;  
4.          **int** hi = hi0;  
5.    
6.          **if** (lo >= hi)  
7.              **return**;  
8.    
9.          // 确定指针方向的逻辑变量  
10.         **boolean** transfer = **true**;  
11.   
12.         **while** (lo != hi) \{  
13.             **if** (a\[lo\] > a\[hi\]) \{  
14.                 // 交换数字  
15.                 **int** temp = a\[lo\];  
16.                 a\[lo\] = a\[hi\];  
17.                 a\[hi\] = temp;  
18.                 // 决定下标移动，还是上标移动  
19.                 transfer = (transfer == **true**) ? **false** : **true**;  
20.             \}  
21.   
22.             // 将指针向前或者向后移动  
23.             **if** (transfer)  
24.                 hi--;  
25.             **else**  
26.                 lo++;  
27.   
28.         \}  
29.   
30.         // 将数组分开两半，确定每个数字的正确位置  
31.         lo--;  
32.         hi++;  
33.         quickSort(a, lo0, lo);  
34.         quickSort(a, hi, hi0);  
35.     \}

[Link 1]: http://blog.csdn.net/aa4790139/article/details/6549120