c语言排序代码实现

关于快速，冒泡，选择，插入等排序，本人用代码实现，均能运行成功。

本文除了排序，针对几种swap函数，也进行了说明，通过汇编代码分析，swap1函数的效率最高。

#include<iostream>
#include <cstdio>

/*交换函数*/
void swap1(int *a,int *b){
　　int tmp = *a;
　　*a = *b;
　　*b = tmp;
}

/**
*swap2和swap3针对同一个变量，会导致这个变量为0
*因为两个指针指向同一个变量。
*/
void swap2(int *a,int *b)
{
　　*a = *a ^ *b;
　　*b = *a ^ *b; //*a ^ *b ^ *b -> *a
　　*a = *a ^ *b; //*a ^ *b ^ *a -> *b
}

void swap3(int *a,int *b)
{
　　*a = *a + *b;
　　*b = *a - *b;
　　*a = *a - *b;
}

void swap3(int &a,int &b){
　　printf("swap3:%d,%d\n",a,b);
　　a = a + b;
　　b = a - b;
　　a = a - b;
　　printf("swap3 end:%d,%d\n",a,b);
}

/*快速排序*/
//不稳定，时间复杂度O(logN) - O(N) 空间复杂度O(1)
void quicksort(int *a,int low,int high)
{

　　int i = low;
　　int j = high;
　　int key = a[low];
　　if(low >= high){
　　return;
　　}
　　while(low < high){
　　　　while(low<high && key <= a[high]){
　　　　　　--high;
　　　　}

　　　　if(key > a[high]){
　　　　　　swap2(&a[low], &a[high]);//交换最低位与最高位置得数据
　　　　　　++low;
　　　　}

　　　　while(low <high && key >= a[low] ){
　　　　　　++low;
　　　　}

　　　　if(key < a[low]){
　　　　　　swap2(&a[low], &a[high]);
　　　　　　--high;
　　　　}
　　　　}
　　　　quicksort(a,i,low-1);
　　　　quicksort(a,low+1,j);
}

/*冒泡排序*/
//稳定，最坏O(N^2) 最好O(N) 空间复杂度O(1)
void maopaoSort(int *a,int size)
{
　　int j,i;
　　for(i=0;i<size;++i){
　　　　for(j=i+1;j<size;++j){
　　　　　　if(a[j] > a[i]){
　　　　　　　　swap2(&a[j],&a[i]);
　　　　　　}
　　　　　}
　　}
}

/*插入排序*/
//稳定，最坏O(N^2) 最好O(N)
void insertSort(int nums[],int size)
{
　　int i,j;
　　for(i=1;i<size;++i){
　　　　int n = nums[i];
　　　　j = i-1;
　　　　while(j>=0&&n>=nums[j]){
　　　　　　nums[j+1] = nums[j];
　　　　　　--j;
　　　　}
　　　　nums[j+1] = n;
　　}
}

/*选择排序*/
//不稳定，最坏O(N^2) 最好O(N)
void selectSort(int *nums,int size)
{
　　int i = 0,j =0;
　　int index = 0;
　　for(i=0;i<size-1;++i){
　　　　index = i;
　　　　for(j=i+1;j<size;++j){
　　　　　　if(nums[index] < nums[j]){
　　　　　　　　index = j;
　　　　　　}
　　　　}
　　　　if(index != i)
　　　　　swap3(nums[index],nums[i]);//使用的是重载的引用类型
　　}
}

void show(int *a,int size)
{
　　std::cout<<"show:"<<std::endl;
　　for(int i=0;i<size;++i){
　　　　std::cout<<a[i]<<" ";
　　}
　　std::cout<<std::endl;
}

int main()
{
　　int arra[] = {100,2,10,11,9,-1000};
　　int size = sizeof(arra)/sizeof(arra[0]);
　　printf("sort start:\n");
　　show(arra, size);
　　selectSort(arra,size);
　　printf("sort end:\n");
　　show(arra, size);
}

巴特西

c语言排序代码实现

最新文章

热门文章