申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111 經濟部所屬事業機構_新進職員甄試_資訊：1.資訊管理 2.程式設計#111338
科目：國營事業◆1.資訊管理 2.程式設計
年份：111年
排序：0

申論題內容

六、快速排序法(Quick Sort)是排序演算中的一種，處理過程是先選擇一個資料為基準點，所有比基準點小的元素放在左邊，比基準點大的元素放在右邊，之後再反覆對基準點左右兩邊的數列執行相同的處理，直到數列只剩一個數值或沒有數值時即完成排序。請撰寫一函式 QuickSort()，將傳入的一維陣列利用快速排序法，由小至大排序陣列元素。（20 分）

詳解 (共 3 筆)

詳解提供者：111郵專一，地特四資訊正取

使用C語言，程式碼如下

void swap(int *x,int *y){
int temp=*x;
*x=*y;
*y=temp;
}

int partition(int a[],int left,int right){
int i,j,pivot;
i=left;
pivot=a[i];
for(j=i+1;j<=right;j++){
if(pivot>=a[j]){
i++; //指在比pivot大的陣列上//
swap(a[i],a[j]);
}
}
a[left]=a[i];
a[i]=pivot;
return i;
}

void quick_sort(int a[],int left,int right){
int mid;
if(left<right){
mid=partition(a,left,right);
quick_sort(a,left,mid-1);
quick_sort(a,mid+1,right);
}
}


int main() {
int n[] = {23,3,12,36,5,11,22,64};
int length=sizeof(n)/sizeof(n[0]);

quick_sort(n,0,7);


for(int z=0;z<length;z++) {
printf("%d,",n[z]);
}
};

詳解提供者：yuC邀請碼196783

C++版本提供參考

詳解提供者：Fourier

順便把每次排序結果給印出來，給剛學資料結構的的人可以對照參考順便理解過程如何運作，輸出結果在底下

程序有問題麻煩請指教

#include <iostream>

using namespace std;

template <typename T, size_t size> //為了印出每次排序結果要呼叫size所以先建個template

void quicksort(T (&array)[size], int left, int right)

{

if (left < right)

{

int i, j, pivot;

i = left;

j = right;

pivot = array[(i+j)/2];

while (1)

{

while (array[i] < pivot && i<right)

{

i++;

}

while (array[j] > pivot && j>left)

{

j--;

}

if (i >= j)

break;

int temp = array[i];

array[i] = array[j];

array[j] = temp;

cout << "當前排序:"; //印出每次排序的結果供參考

for (int k = 0; k < size; k++)

{

cout << array[k] << " ";

}

cout << endl;

}

quicksort(array, left, i-1);

quicksort(array, i + 1, right);

}

int main()

{

int data[10] = {2, 3, 4, 5, 1, 6, 0, 8, 9, 7};

quicksort(data, 0, 9);

return 0;

}

輸出結果: