1、冒泡排序
*/
//冒泡 时间复杂度O（n^2）
/*
第一次:从一个数组的最后一个元素到该数组的第一个元素进行扫描，比较后一个元素与前一个元素的大小，如果后一个小于前一个，交换顺序。通过这样的交换，那么我们就可以把该数组的最小元素换位到该数组的第一个位置。
第二次:从该数组的最后一个元素到该数组的第二个元素进行扫描，比较后一个元素与前一个元素的大小，如果后一个小于前一个，交换顺序。通过这样的交换，那么我们就可以把该数组的最小元素换位到该数组的第二个位置。 依次这样的循环。。。。
如果是有n个元素的话，那么我们就要进行n-1次的冒泡，就可以把该数组从小到大排好序
*/
void print(int *num,int n){
for (int i = 0; i < n; i++) {
printf("%d ",num[i]);
}
printf("\n");
return;
}
//最大的搁最后
void bubble_Sort(int *num,int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (num[j] > num[j + 1]) {
int temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
print(num, n);
}
int main() {
@autoreleasepool {
int n = 0;
NSLog(@"请输入需要排序的个数n：");
scanf("%d",&n);//输入函数不要带n = ？
NSLog(@"n = %d",n);
// printf("n = %d",n);
int num[] = {0};
for (int i = 0; i < n; i++) {
num[i] = arc4random() % 10;
// NSLog(@"请输入第%d个数：",i+1);
}
// int num[5] = {54,32,49,78,89};
bubble_Sort(num, 5);
}
return 0;
}
2、直接插入排序
//插入排序事件复杂度O（n^2）
//待排序元素用数组a表示 n表示数组有n个元素
void insert_sort(int* a,int n){
int i,j;
int temp;
for (i = 1; i < n; i++) {//i 表示插入次数 共插入n-1次
temp = a[i];//把待排序元素赋给temp，temp在while循环中并不改变，这样方便比较，并且它是要插入的元素
j = i - 1;
while (temp < a[j]) {
//while循环的作用是将比当前元素大的元素都往后移动一个位置
a[j+1] = a[j];
j--;// 顺序比较并移动,依次将元素后移一个位置
}
a[j+1] = temp;//元素后移后要插入的位置就空出了，找到该位置插入
}
}
int main(){
@autoreleasepool {
int array[] = {4,9,8,30,20,50};
int i = 0;
insert_sort(array,6);
for (i = 0; i < 6; i++) {
printf("[%d]\n",array[i]);
}
}
return 0;
}
3、希尔（插入）排序
/*
希尔排序（Shell sort）基本思想: 改进的直接插入算法。设待排序的元素序列有n个元素，首先取一整数gap（<n）作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素放在同一序列中，在每个子序列中分别进行直接插入排序。然后缩小gap，例如gap=gap/2,重复上述的子序列划分与排序工作。开始由于gap取直大，每个子序列元素少，排序速度快，待排序后期，gap值逐渐变小，子序列元素变多，但由于前面的工作基础，大多数元素已经有序，所以排序速度快。
基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
希尔排序是一种不稳定的排序。
在最优的情况下，时间复杂度为：O（n ^ (1.3) ）（元素已经排序好顺序）
O(nlog n)
在最差的情况下，时间复杂度为：O（n ^ 2）；
*/
void swap(int *a,int *b){//指针值交换算法
int x;
x = *a;
*a = *b;
*b = x;
}
void insertion_sort(int data[], int n, int increment)
{
int i, j;
for (i = increment; i < n; i += increment)
{
for (j = i; j >= increment; j -= increment)
{
if (data[j] < data[j-increment])
{
swap(&data[j], &data[j-increment]);
}
}
}
}
void shellsort(int data[], int n)
{
int i, j;
for (i = n / 2; i > 0; i /= 2)//每次缩短一半
{
for (j = 0; j < i; j++)
{
insertion_sort(data, n, i);//第一次i = n / 2
}
}
}
int main(){
@autoreleasepool {
// int a = 10;
// int * pa = &a;
// printf("%d",*pa);
int data[] = {1,3,5,4,9,6,7,8,2};
shellsort(data, 9);
int data2[] = {0};
for (int i = 0;i < 100 ; i++) {
data2[i] = arc4random() % 100;//%余数 ／整数
}
shellsort(data2, 100);
for (int i = 0; i < 9; i++) {
// printf("[%d]\n",data[i]);
}
for (int i = 0; i < 100; i++) {
printf("[%d]\n",data2[i]);
}
}
return 0;
}
4、二分（插入）排序
/*
二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
平均时间复杂度O(n^2)
*/
//折半插入
#define KeyType int
typedef struct _SeqList
{
int key;
}SeqList;
int Partition0( int R[], int i, int j){//调用Partition(R,low,high)时,对R[low..high]做划分,
int pivot = R[i];//用区间的第1个记录作为基准
while( i < j )// i == 0,j == 9条件为真
{
if (R[j] >= pivot) {
j--;//从右向左扫描,查找第1个关键字小于pivot的记录R[j]
}
R[i] = R[j];//相当于交换R[i]和R[j]
if (R[i] <= pivot) {
i++;//从左向右扫描,查找第1个关键字大于pivot的记录R[i]
}
R[j] = R[i];//相当于交换R[i]和R[j]
}
R[i]=pivot;
return i;
}
//结构体写法
int Partition( SeqList R[], int i, int j){//调用Partition(R,low,high)时,对R[low..high]做划分,
SeqList pivot = R[i];// 用区间的第1个记录作为基准
while( i < j )
{
while( i < j && R[j].key >= pivot.key )//pivot相当于在位置i上
{
j--;//从右向左扫描,查找第1个关键字小于pivot.key的记录R[j]
}
if( i < j )//表示找到的R[j]的关键字<pivot.key
{
R[i] = R[j];//相当于交换R[i]和R[j],交换后i指针加1
}
while( i < j && R[i].key <= pivot.key )//pivot相当于在位置j上
{
i++;//从左向右扫描,查找第1个关键字大于pivot.key的记录R[i]
}
if( i < j )//表示找到了R[i],使R[i].key>pivot.key
{
R[j] = R[i];//相当于交换R[i]和R[j]
}
}
R[i]=pivot;
return i;
}
void QuickSort0( int R[], int low, int high )
{
int pivotpos; // 划分后的基准记录的位置
if( low < high )
{// 仅当区间长度大于1时才须排序
pivotpos = Partition0(R, low, high);//对R[low..high]做划分
QuickSort0( R, low, pivotpos - 1 );//对左区间递归排序
QuickSort0( R, pivotpos + 1, high );//对右区间递归排序
}
}
//结构体写法
void QuickSort( SeqList R[], int low, int high )
{
int pivotpos; // 划分后的基准记录的位置
if( low < high )
{// 仅当区间长度大于1时才须排序
pivotpos = Partition(R, low, high);//对R[low..high]做划分
QuickSort( R, low, pivotpos - 1 );//对左区间递归排序
QuickSort( R, pivotpos + 1, high );//对右区间递归排序
}
}
int main(){
@autoreleasepool {
SeqList arr_Seq[10];
int arr[] ={5,2,6,7,3,12,56,0,15,22};
for (int i = 0; i < 10; i++) {
arr_Seq[i].key = arr[i];
}
QuickSort0(arr, 0, 9);
//结构体写法
QuickSort( arr_Seq, 0, 9 );
for( int i = 0; i < 10; i++ )
{
printf("%d\n",arr[i]);
//结构体写法
printf("%d\n",arr_Seq[i].key);
printf("====================\n");
}
}
return 0;
}
5、选择排序
/*
简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
时间复杂度为O(n2)
*/
void SelectSort(int r[], int length)/*对记录数组r做简单选择排序，length为待排序记录的个数*/
{
for (int i=0 ; i< length-1 ; i++) //n-1趟排序
{
int index = i;//假设index处对应的数组元素是最小的
for (int j = i+1 ; j < length ; j++)//查找最小记录的位置
if (r[j] < r[index] )
index = j;
if ( index != i)//若无序区第一个元素不是无序区中最小元素，则进行交换
{
// r[i] = r[i] + r[index];
// r[index] = r[i] - r[index];
// r[i] = r[i] - r[index];
r[i] = r[index];
}
}
}
int main(){
@autoreleasepool {
int r[] = {0};
for (int i = 0; i < 10; i++) {
r[i] = arc4random() % 100;
}
SelectSort(r, 10);
for (int i = 0; i < 10; i++) {
printf("%d\n",r[i]);
}
}
return 0;
}
6、快速排序
/*
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
*/
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];//一般第一个数作为第一趟比较数据
while(i < j)/*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是
1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）
2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
int main(){
@autoreleasepool {
int r[] = {0};
for (int i = 0; i < 10; i++) {
r[i] = arc4random() % 10;
}
sort(r, 0, 10);
for (int i = 0; i < 10; i++) {
printf("%d\n",r[i]);
}
}
return 0;
}
7、堆排序
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
int nChild;
int nTemp;
for(;2*i+1<nLength;i=nChild)
{
//子结点的位置=2*（父结点位置）+1
nChild=2*i+1;
//得到子结点中较大的结点
if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if(array[i]<array[nChild])
{
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}
else break; //否则退出循环
}
}
//堆排序算法
void HeapSort(int array[],int length)
{
int i;
//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点，此处"/"为整除
for(i=length/2-1;i>=0;--i)
HeapAdjust(array,i,length);
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i)
{
//把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i]=array[0]^array[i];
array[0]=array[0]^array[i];
array[i]=array[0]^array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}
int main(){
@autoreleasepool {
int i;
int num[]={9,8,7,6,5,4,3,2,1,0};
HeapSort(num,sizeof(num)/sizeof(int));
for(i=0;i<sizeof(num)/sizeof(int);i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
return 0;
}
8、归并排序
/*
归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
*/
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = (startIndex + endIndex) / 2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
int main(){
@autoreleasepool {
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
}
return 0;
}
9、基数排序
- (void)testBS
{
int a[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
int *a_p = a;
//计算数组长度
int size = sizeof(a) / sizeof(int);
//基数排序
bucketSort3(a_p, size);
//打印排序后结果
int i;
for(i = 0; i < size; i++)
{
printf("%d\n", a[i]);
}
int t;
scanf("%d", t);
}
//基数排序
voidbucketSort3(int *p, int n)
{
//获取数组中的最大数
int maxNum = findMaxNum(p, n);
//获取最大数的位数，次数也是再分配的次数。
int loopTimes = getLoopTimes(maxNum);
int i;
//对每一位进行桶分配
for(i = 1; i <= loopTimes; i++)
{
sort2(p, n, i);
}
}
//获取数字的位数
intgetLoopTimes(intnum)
{
int count = 1;
int temp = num / 10;
while(temp != 0)
{
count++;
temp = temp / 10;
}
returncount;
}
//查询数组中的最大数
intfindMaxNum(int *p, intn)
{
int i;
int max = 0;
for(i = 0; i < n; i++)
{
if(*(p + i) > max)
{
max = *(p + i);
}
}
return max;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int *p, int n, int loop)
{
//建立一组桶此处的20是预设的根据实际数情况修改
intbuckets[10][20] = {};
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
inttempNum = (int)pow(10, loop - 1);
inti, j;
for(i = 0; i < n; i++)
{
introw_index = (*(p + i) / tempNum) % 10;
for(j = 0; j < 20; j++)
{
if(buckets[row_index][j] == NULL)
{
buckets[row_index][j] = *(p + i);
break;
}
}
}
//将桶中的数，倒回到原有数组中
intk = 0;
for(i = 0; i < 10; i++)
{
for(j = 0; j < 20; j++)
{
if(buckets[i][j] != NULL)
{
*(p + k) = buckets[i][j];
buckets[i][j] = NULL;
k++;
}
}
}
}
int main(){
@autoreleasepool {
}
return 0;
}
网友评论