插图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;
}
// Swift
func insertSort(_ nums:inout [Int]){
let length = nums.count
if nums.count <= 1 {
return
}
for i in 1..<length {
if nums[i] < nums[i-1] {
let temp = nums[i]
var j = i - 1
while j >= 0 && temp < nums[j] {
nums[j+1] = nums[j]
j = j - 1
}
nums[j+1] = temp
}
}
}
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(清华大学出版社，严蔚敏)*/
java解法
原文链接：https://blog.csdn.net/nrsc272420199/article/details/82587933
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
quickSort(arr, 0, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
}
快速排序时间复杂度为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)。它是不稳定的排序方法。
归并排序
用到了分而治之的思想，非常厉害的排序算法，很有必要理解，在一些Leetcode中的题目中会有用到相似的算法。
参考文章：[https://www.cnblogs.com/chengxiao/p/6194356.html](https://www.cnblogs.com/chengxiao/p/6194356.html)
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
