常考的数据结构与算法之算法
2018-06-10 本文已影响138人
EchooJ
插图n.jpg
本文记录一下我学习数据结构与算法中算法的知识点，使用的语言是C/C++语言
查找
二分查找
又叫折半查找，要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while(left<=right)
{
mid=(left+right)/2;
if(key==Array[mid]) return mid;
else if(key<Array[mid]) right=mid-1;
else if(key>Array[mid]) left=mid+1;
}
return -1;
}
排序
就是重新排列表中的元素
各个排序算法的比较.png
1. 插入排序
直接插入排序
#include<iostream>
using namespace std;
int main()
{
int a[]={98,76,109,34,67,190,80,12,14,89,1};
int k=sizeof(a)/sizeof(a[0]);
int j;
for(int i=1;i<k;i++)//循环从第2个元素开始
{
if(a[i]<a[i-1])
{
int temp=a[I];
for(j=i-1;j>=0 && a[j]>temp;j--)
{
a[j+1]=a[j];
}
a[j+1]=temp;//此处就是a[j+1]=temp;
}
}
for(int f=0;f<k;f++)
{
cout<<a[f]<<" ";
}
return 0;
}
2. 交换排序
（1）冒泡排序
#include <stdio.h>
#define SIZE 8
void bubble_sort(int a[], int n);
void bubble_sort(int a[], int n)
{
int i, j, temp;
for (j = 0; j < n - 1; j++)
for (i = 0; i < n - 1 - j; i++)
{
if(a[i] > a[i + 1])
{
temp = a[I];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
int main()
{
int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
int I;
bubble_sort(number, SIZE);
for (i = 0; i < SIZE; I++)
{
printf("%d", number[I]);
printf("\n");
}
}
(2)快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); I++)
{
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/
快速排序时间复杂度为O(n2)，空间复杂度为O(nlogn)。它是不稳定的排序方法。
选择排序
简单选择排序
感觉一般不考这个，但是比较简单还是列一下，考的比较多的是堆排序
//数据结构课本上的算法
void Select_Sort(datatype R[],int n)
{ //对排序表R[1].....R[n]进行冒泡排法，n是记录个数
for(i=1; i<n; i++) /*做n-1趟选取*/
{
k=i; /*在i开始的n-i+1个记录中选关键码最小的记录*/
for(j=i+1;j<=n;j++)
if(R[j].key<R[k].key)
k=j; /*k中存放关键码最小记录的下标*/
if(i!=k) /*关键码最小的记录与第i个记录交换*/
{
int temp;
temp=R[k];
R[k]=R[I];
R[i]=temp；
}
}
}
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
堆排序的介绍写的比较好的文章是图解排序算法之堆排序
#include <stdio.h>
void swap(int *a, int *b);
void adjustHeap(int param1,int j, int inNums[]);
void HeapSort(int nums, int inNums[]);
//大根堆进行调整
void adjustHeap(int param1, int j, int inNums[])
{
int temp=inNums[param1];
for (int k=param1*2+1;k<j;k=k*2+1)
{
//如果右边值大于左边值，指向右边
if (k+1<j && inNums[k]< inNums[k+1])
{
k++;
}
//如果子节点大于父节点，将子节点值赋给父节点,并以新的子节点作为父节点（不用进行交换）
if (inNums[k]>temp)
{
inNums[param1]=inNums[k];
param1=k;
}
else
break;
}
//put the value in the final position
inNums[param1]=temp;
}
//堆排序主要算法
void HeapSort(int nums,int inNums[])
{
//1.构建大顶堆
for (int i=nums/2-1;i>=0;i--)
{
//put the value in the final position
adjustHeap(i,nums,inNums);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j=nums-1;j>0;j--)
{
//堆顶元素和末尾元素进行交换
int temp=inNums[0];
inNums[0]=inNums[j];
inNums[j]=temp;
adjustHeap(0,j,inNums);//重新对堆进行调整
}
}
int main() {
int data[] = {6,5,8,4,7,9,1,3,2};
int len = sizeof(data) / sizeof(int);
HeapSort(len,data);
return 0;
}
堆排序时间复杂度为O(nlogn)，空间复杂度为O(1)。它是不稳定的排序方法。
