說明
請看看之前介紹過的氣泡排序法：
for(i = 0; i < MAX-1 && flag == 1; i++) {
flag = 0;
for(j = 0; j < MAX-i-1; j++) {
if(number[j+1] < number[j]) {
SWAP(number[j+1], number[j]);
flag = 1;
}
}
}
事實上這個氣泡排序法已經不是單純的氣泡排序了，它使用了旗標與右端左移兩個方法來改進排序的效能，而Shaker排序法使用到後面這個觀念進一步改良氣泡排序法。
解法
在上面的氣泡排序法中，交換的動作並不會一直進行至陣列的最後一個，而是會進行至MAX-i-1，所以排序的過程中，陣列右方排序好的元素會一直增加，使得左邊排序的次數逐漸減少，如我們的例子所示：
排序前：95 27 90 49 80 58 6 9 18 50
- 27 90 49 80 58 6 9 18 50 [95] 95浮出
- 27 49 80 58 6 9 18 50 [90 95] 90浮出
- 27 49 58 6 9 18 50 [80 90 95] 80浮出
- 27 49 6 9 18 50 [58 80 90 95] ......
- 27 6 9 18 49 [50 58 80 90 95] ......
- 6 9 18 27 [49 50 58 80 90 95] ......
- 6 9 18 [27 49 50 58 80 90 95]
方括號括住的部份表示已排序完畢，Shaker排序使用了這個概念，如果讓左邊的元素也具有這樣的性質，讓左右兩邊的元素都能先排序完成，如此未排序的元素會集中在中間，由於左右兩邊同時排序，中間未排序的部份將會很快的減少。
方法就在於氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行，如此完成一次排序的動作，而您必須使用left與right兩個旗標來記錄左右兩端已排序的元素位置。
一個排序的例子如下所示：
排序前：45 19 77 81 13 28 18 19 77 11
往右排序：19 45 77 13 28 18 19 77 11 [81]
向左排序：[11] 19 45 77 13 28 18 19 77 [81]
往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]
往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]
往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]
如上所示，括號中表示左右兩邊已排序完成的部份，當left > right時，則排序完成。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void shakerSort(int[]);
int main(void) {
srand(time(NULL));
int number[MAX] = {0};
printf("排序前：");
int i;
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
shakerSort(number);
printf("\n排序後：");
for(i = 0; i < MAX; i++) {
printf("%d ", number[i]);
}
return 0;
}
void shakerSort(int number[]) {
int left = 0, right = MAX - 1, shift = 0;
while(left < right) {
// 向右進行氣泡排序
int i;
for(i = left; i < right; i++) {
if(number[i] > number[i+1]) {
SWAP(number[i], number[i+1]);
shift = i;
}
}
right = shift;
// 向左進行氣泡排序
int k;
for(k = right; k > left; k--) {
if(number[k] < number[k-1]) {
SWAP(number[k], number[k-1]);
shift = k;
}
}
left = shift;
}
}
public class Sort {
public static void sort(int[] number) {
int left = 0;
int right = number.length - 1;
int shift = 0;
while(left < right) {
// 向右進行氣泡排序
for(int i = left; i < right; i++) {
if(number[i] > number[i+1]) {
swap(number, i, i+1);
shift = i;
}
}
right = shift;
// 向左進行氣泡排序
for(int i = right; i > left; i--) {
if(number[i] < number[i-1]) {
swap(number, i ,i-1);
shift = i;
}
}
left = shift;
}
}
private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
def sort(number):
left = 0
right = len(number) - 1
shift = 0
while left < right:
for i in range(left, right):
if number[i] > number[i + 1]:
number[i], number[i + 1] = number[i + 1], number[i]
shift = i
right = shift
for i in range(right, left, -1):
if number[i] < number[i - 1]:
number[i], number[i - 1] = number[i - 1], number[i]
shift = i
left = shift
object Sort {
def shark(number: Array[Int]) {
var left = 0
var right = number.length - 1
var shift = 0
while(left < right) {
for(i <- left until right if number(i) > number(i + 1)) {
swap(number, i, i + 1)
shift = i
}
right = shift
for(i <- right until left if number(i) > number(i - 1)) {
swap(number, i, i - 1)
shift = i
}
left = shift
}
}
private def swap(number: Array[Int], i: Int, j: Int) {
val t = number(i)
number(i) = number(j)
number(j) = t
}
}
def sort(number)
left = 0
right = number.length - 1
shift = 0
while left < right
left.upto(right - 1) { |i|
if number[i] > number[i + 1]
number[i], number[i + 1] = number[i + 1], number[i]
shift = i
end
}
right = shift
right.downto(left + 1) { |i|
if number[i] < number[i - 1]
number[i], number[i - 1] = number[i - 1], number[i]
shift = i
end
}
left = shift
end
end
|
|