目的
学习关于排序的一些算法以及运用
技术及其使用
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); // 放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
}
}
} int main()
{ int A[] = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }; // 从小到大选择排序
int n = sizeof(A) / sizeof(int);
SelectionSort(A, n);
printf("选择排序结果："); 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; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
}
} int main()
{ int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
int n = sizeof(A) / sizeof(int);
InsertionSort(A, n);
printf("插入排序结果："); for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n"); return 0;
}
4.c++随机生成整数
rand()和srand()要一起使用，其中srand()用来初始化随机数种子,rand()用来产生随机数.
因为默认情况下随机数种子为1，而相同的随机数种子产生的随机数是一样的,失去了随机性的意义，所以为使每次得到的随机数不一样，用函数srand()初始化随机数种子。srand()的参数，用time函数值（即当前时间），因为两次调用rand()函数的时间通常是不同的，这样就可以保证随机性了。
int main()
{
int i;
srand((unsigned)time(NULL)); //初始化随机数种子
for (i=0; i<10; i++) //产生10个随机整数(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;
}
(创建一个有4个整数数组，每个数都是随机的一到十的整数，消除重复后进行冒泡排序（本代码使用的是分部实现功能，较臃肿需改进，但基本思想已包含）)
