首页 > 编程语言 > 详细

c语言排序代码实现

时间:2019-09-14 12:59:01      阅读:60      评论:0      收藏:0      [点我收藏+]

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

本文除了排序,针对几种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语言排序代码实现

原文:https://www.cnblogs.com/jfyl1573/p/11518750.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!