目的
學習關(guān)于排序的一些算法以及運用
技術(shù)及其使用
1.冒泡排序
void bubbleSort(int A[],int n){
int temp;
int i,j;
for(i = 0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
}
2.選擇排序
#include <stdio.h>
void Swap(int A[], int i, int j)
{ int temp = A[i];
A[i] = A[j];
A[j] = temp;
} void SelectionSort(int A[], int n)
{ for (int i = 0; i < n - 1; i++) // i為已排序序列的末尾
{ int min = i; for (int j = i + 1; j < n; j++) // 未排序序列
{ if (A[j] < A[min]) // 找出未排序序列中的最小值
{
min = j;
}
} if (min != i)
{
Swap(A, min, i); // 放到已排序序列的末尾，該操作很有可能把穩(wěn)定性打亂，所以選擇排序是不穩(wěn)定的排序算法
}
}
} int main()
{ int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 從小到大選擇排序
int n = sizeof(A) / sizeof(int);
SelectionSort(A, n);
printf("選擇排序結(jié)果："); for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n"); return 0;
}
3.插入排序
#include <stdio.h>
void InsertionSort(int A[], int n)
{ for (int i = 1; i < n; i++) // 類似抓撲克牌排序
{ int get = A[i]; // 右手抓到一張撲克牌
int j = i - 1; // 拿在左手上的牌總是排序好的
while (j >= 0 && A[j] > get) // 將抓到的牌與手牌從右向左進行比較
{
A[j + 1] = A[j]; // 如果該手牌比抓到的牌大，就將其右移
j--;
}
A[j + 1] = get; // 直到該手牌比抓到的牌小(或二者相等)，將抓到的牌插入到該手牌右邊(相等元素的相對次序未變，所以插入排序是穩(wěn)定的)
}
} int main()
{ int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 從小到大插入排序
int n = sizeof(A) / sizeof(int);
InsertionSort(A, n);
printf("插入排序結(jié)果："); for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n"); return 0;
}
4.c++隨機生成整數(shù)
rand()和srand()要一起使用，其中srand()用來初始化隨機數(shù)種子,rand()用來產(chǎn)生隨機數(shù).
因為默認情況下隨機數(shù)種子為1，而相同的隨機數(shù)種子產(chǎn)生的隨機數(shù)是一樣的,失去了隨機性的意義，所以為使每次得到的隨機數(shù)不一樣，用函數(shù)srand()初始化隨機數(shù)種子。srand()的參數(shù)，用time函數(shù)值（即當前時間），因為兩次調(diào)用rand()函數(shù)的時間通常是不同的，這樣就可以保證隨機性了。
int main()
{
int i;
srand((unsigned)time(NULL)); //初始化隨機數(shù)種子
for (i=0; i<10; i++) //產(chǎn)生10個隨機整數(shù)(0-10)
{
printf("%d",rand()%10);
}
return 0;
}
實際使用
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
int main()
{
srand((unsigned int)time(NULL));
int originalarray[4] = {0};
int changedarray[4] = {0};
int buffer[4] = {0};
int temp = 0;
int i=0, j=0, k=0;
for (j = 0; j < 4; j++)
{
for (i = rand() % 10; buffer[i] == 1; i = rand() % 10);
originalarray[j] = i; buffer[i] = 1;
printf("%d ", originalarray[j]);
}
printf("\n");
for ( k = 0; k < 3; k++) {
for( j =3;j>0;j--){
if (originalarray[j] < originalarray[j - 1]) {
temp = originalarray[j];
originalarray[j] = originalarray[j - 1];
originalarray[j - 1] = temp;
}
}
}
for ( i = 0; i < 4; i++) {
printf("%d ",originalarray[i]);
}
return 0;
}
(創(chuàng)建一個有4個整數(shù)數(shù)組，每個數(shù)都是隨機的一到十的整數(shù)，消除重復后進行冒泡排序（本代碼使用的是分部實現(xiàn)功能，較臃腫需改進，但基本思想已包含）)
