排序

 

1.冒泡排序

通过两个数之间进行大小比较,较大的数下沉,较小的数上浮,通过不断的比较来调整位置。

Void bubblesort(int arr[] )
{
  Int temp;
  For(int i=0;i<arr.length()-1;i++)
    For(int j=arr.length()-;j>I;j--)
      If(arr[j]<arr[i]){
        swap(arr[i],arr[j]);
      }
}

时间复杂度:O(n^2)

2.简单选择排序

从开始一直枚举到最后,每次取其中最小的的元素,放在最前面,不断形成一个有序的排列。

void selectcode(){
for(int i=0;i<n;i++){
   k=i;
   for(int j=i;j<n;j++)
      if(a[k]>a[j]) k=j;
   swap(a[k],a[i]);
}

逻辑简单,在不考虑时间复杂度的情况下,可以不用动脑子,但是时间复杂度相对来讲比较高为,O(n^2)

3.直接插入排序

从第二位开始,每次从无序的数组中,取出第一个在有序的数组中找到它的位置,将它放在其中,在它后面的数都往后移一个位置。

void insertcode(){
   for(int i=1;i<n;i++){
      int temp=a[i],j=i;//temp为需要变化的数
      while(j>1&&temp<a[j-1]){
         a[j]=a[j-1];   //数组往后移一位
         j--;
      }
      a[j]=temp;
   }
}

4.归并排序

简单的来讲一下2-路归并排序。原理就是就序列两两分组,组内先进行排序;然后将这些组再两两归并,组内在排序;一直进行下去只到只剩下一个组为止。时间复杂度为O(nlogn)

void merge(int a[], int l1,int r1,int l2,int r2) //两个序列合并
void mergesort(int a[], int left ,int rght)
{
   if(left<right){
      int mid = (left + right)/2;
      mergesort(a, left ,mid);
      mergesort(a, mid+1 ,right);
      merge(a, left ,mid+1,right);
}
      

5.快速排序

通过选定一个元素,左右调换位置(先从右边开始一直找到一个小于该元素的一个数,放到该元素的位置,这个元素放到小于该元素的数的位置上面,先从左边开始一直找到一个大于该元素的一个数,放到该元素的位置,这个元素放到大于该元素的数的位置上面,),使得它的左侧元素都不超过它,它右侧元素都不小于它,不断的调整使得每一个元素最终处在自己的位置上。

int partition(int a[], int left, int right)
{
   int temp = a[left];
   while(left < right){
      while(left < right && a[right] > temp) right--;
      a[left] = a[right];
      while(left < right && a[right] <= temp) left++;
      a[right] = a[left];
   }
   a[left] = temp ;
   return left;    //返回这个元素的正确位置
}

void quicksort(int a[], int left, int right){
   if(left < right){
      int pos = partition(a, left, right);
      quicksort(a ,left, pos -1);
      quicksort(a ,pos+1, right);
   }
}

 

C++ 指针与动态内存分配

动态分配内存

例: int * ptr_int = new int ; 在运行阶段为一个int分配未命名的内存

使用指针来访问这个值

Delete ptr_int;//释放内存(删除数组时要在delete后面加[])

在运行的时候,才给它分配空间

Ps:不要创建两个指向同一内存块的指针,有可能误删两次

 

栈区(stack)

由编译器自动分配释放,一般存放函数参数值、局部变量值

操作方式类似数据结构中的栈

堆区(heap)

程序员自己分配释放,若程序不释放,程序结束可能由操作系统回收

分配方式类似链表

全局区(static)

全局变量和静态变量是存储在一起的

程序结束后由系统释放

文字常量区

存放常量字符串,结束后由系统释放

程序代码区

存放函数体的二进制代码

例:

Int num1 =0;//全局初始化区
Int * ptr1;//全局未初始化区
Int main()
{
	Int num2;//栈区
	Char str[] =”123”;//栈区
	Char * ptr2;//栈区
	Char * ptr3 =”13”;//13在常量区、ptr3在栈区
	Static int num3 =1024;//全局区
	ptr1 = new int[10];
	ptr2 = new char[20];//两者分配的内存在堆区
	return 0;
}

指针用来存放一个内存地址  内存大小4B

定义一个一维数组 数组名为数组的首地址

首地址:一段内存空间中第一个存储单元的地址。最大的存储单元

Int a[5]; a指向a[0],a的类型就是            int*

&a 这个地址指向整个人数组的类型  int(*)[5]

当指针加上*的时候,可以想成读取这个指针所指向的这个地址的值

数组指针  是数组首元素地址的指针,同时也是指向整个数组的指针 &a的

访问数组元素  下标法:a[i]

指针法:*p++

数组名是这个数组的首地址不能够随意改变

二维数组 int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};

A是指想a[0]这个一维数组。Int(*)[4]

a[0]指向a[0][0]  a[0]的类型是int*

二维数组表达 a[m][n]

*(a[m]+n)

*(*(a+m)+n)

Int a[3][4]

a      int(*)[4];

&a    int(*)[3][4]

a[0]   int*

a[0][0] int

野指针:不能明确指向的指针变量(危险)

指针变量的运算  更多用于指针偏移,去访问地址旁边的一些内存

指针的加减以指针所指向的类型空间为单位进行偏移