选择排序的基本实现步骤:
- 从待排序序列中找到最小(或最大)的元素。
- 将找到的最小元素与待排序序列的第一个元素交换位置,即将其放置到已排序序列的末尾。
- 在剩余未排序元素中继续找到最小(或最大)元素,然后与待排序序列的第二个元素交换位置。
- 重复以上步骤,直到所有元素均排序完毕。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
typedef int ElemType;
typedef struct {
ElemType *elem;
int TableLen;
} SSTable;
void ST_Init(SSTable &ST, int len) {
ST.TableLen = len;
ST.elem = (ElemType *) malloc(ST.TableLen * sizeof(ElemType));
int i;
srand(time(NULL));
for (int i = 0; i < ST.TableLen; ++i) {
ST.elem[i] = rand() % 100;
}
}
void ST_print(SSTable ST) {
for (int i = 0; i < ST.TableLen; ++i) {
printf("%d ", ST.elem[i]);
}
printf("\n");
}
void swap(ElemType &a, ElemType &b) {
ElemType tmp;
tmp = a;
a = b;
b = tmp;
}
void BubbleSort(ElemType A[], int n) {
int i, j;
bool flag;
for (i = 0; i < n - 1; i++)
{
flag = false;
for (j = n - 1; j > i; j--)
{
if (A[j - 1] > A[j]) {
swap(A[j - 1], A[j]);
flag = true;
}
}
if (false == flag)
return;
}
}
int partition(ElemType *A, int low,int high) {
ElemType pivot=A[low];
while (low<high){
while (low<high&&A[high]>=pivot)
high--;
A[low]=A[high];
while (low<high&&A[low]<=pivot)
low++;
A[high]=A[low];
}
A[low]= pivot;
return low;
}
void QuickSort(ElemType *A, int low,int high) {
if(low<high) {
int pivot_pos = partition(A, low, high);
QuickSort(A, low, pivot_pos - 1);
QuickSort(A, pivot_pos + 1, high);
}
}
void InsertSort(ElemType *A,int n){
int inserVal,i,j;
for (i= 1; i<n ;i ++) {
inserVal=A[i];
for (j = i-1; j >=0&&A[j]>inserVal ; j--) {
A[j+1]=A[j];
}
A[j+1]=inserVal;
}
}
void SelectSort(ElemType A[],int n){
int min;
for (int i = 0; i < n; ++i) {
min=i;
for (int j = i+1; j <n ; ++j) {
if(A[j]<A[min]){
min=j;
}
}
if(min!=i){
swap(A[i],A[min]);
}
}
}
void SelectSort1(ElemType A[],int n){
int max;
for (int i = n-1; i >= 0; --i) {
max=i;
for (int j = 0;j<i ; ++j) {
if(A[j]>A[max]){
max=j;
}
}
if(max!=i){
swap(A[i],A[max]);
}
}
}
int main() {
SSTable ST;
ST_Init(ST, 10);
ElemType a[10] = {12, 22, 18, 64, 69, 84, 79, 95, 94, 78};
ST_print(ST);
SelectSort(ST.elem,10);
ST_print(ST);
return 0;
}