插圖n.jpg
本文記錄一下我學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法中算法的知識(shí)點(diǎn)，使用的語言是C/C++語言
查找
二分查找
又叫折半查找规惰，要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列庐船。
首先，假設(shè)表中元素是按升序排列嘲更，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較醉鳖，如果兩者相等，則查找成功哮内；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字北发，則進(jìn)一步查找前一子表纹因，否則進(jìn)一步查找后一子表。重復(fù)以上過程琳拨，直到找到滿足條件的記錄瞭恰，使查找成功，或直到子表不存在為止狱庇，此時(shí)查找不成功惊畏。
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;
}
排序
就是重新排列表中的元素
各個(gè)排序算法的比較.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++)//循環(huán)從第2個(gè)元素開始
{
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)快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小密任，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序颜启，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列浪讳。
#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];/*用字表的第一個(gè)記錄作為樞軸*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*將比第一個(gè)小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*將比第一個(gè)大的移到高端*/
}
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);/*這里原文第三個(gè)參數(shù)要減1否則內(nèi)存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); I++)
{
cout << a[i] << "";
}
return 0;
}/*參考數(shù)據(jù)結(jié)構(gòu)p274(清華大學(xué)出版社缰盏，嚴(yán)蔚敏)*/
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) {
// 找尋基準(zhǔn)數(shù)據(jù)的正確索引
int index = getIndex(arr, low, high);
// 進(jìn)行迭代對(duì)index之前和之后的數(shù)組進(jìn)行相同的操作使整個(gè)數(shù)組變成有序
quickSort(arr, 0, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基準(zhǔn)數(shù)據(jù)
int tmp = arr[low];
while (low < high) {
// 當(dāng)隊(duì)尾的元素大于等于基準(zhǔn)數(shù)據(jù)時(shí),向前挪動(dòng)high指針
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果隊(duì)尾元素小于tmp了,需要將其賦值給low
arr[low] = arr[high];
// 當(dāng)隊(duì)首元素小于等于tmp時(shí),向前挪動(dòng)low指針
while (low < high && arr[low] <= tmp) {
low++;
}
// 當(dāng)隊(duì)首元素大于tmp時(shí),需要將其賦值給high
arr[high] = arr[low];
}
// 跳出循環(huán)時(shí)low和high相等,此時(shí)的low或high就是tmp的正確索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要將tmp賦值給arr[low]
arr[low] = tmp;
return low; // 返回tmp的正確位置
}
}
快速排序時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(nlogn)淹遵。它是不穩(wěn)定的排序方法口猜。
選擇排序
簡(jiǎn)單選擇排序
感覺一般不考這個(gè)，但是比較簡(jiǎn)單還是列一下透揣，考的比較多的是堆排序
//數(shù)據(jù)結(jié)構(gòu)課本上的算法
void Select_Sort(datatype R[],int n)
{ //對(duì)排序表R[1].....R[n]進(jìn)行冒泡排法济炎，n是記錄個(gè)數(shù)
for(i=1; i<n; i++) /*做n-1趟選取*/
{
k=i; /*在i開始的n-i+1個(gè)記錄中選關(guān)鍵碼最小的記錄*/
for(j=i+1;j<=n;j++)
if(R[j].key<R[k].key)
k=j; /*k中存放關(guān)鍵碼最小記錄的下標(biāo)*/
if(i!=k) /*關(guān)鍵碼最小的記錄與第i個(gè)記錄交換*/
{
int temp;
temp=R[k];
R[k]=R[I];
R[i]=temp；
}
}
}
堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法辐真，它是選擇排序的一種须尚。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素拆祈。堆分為大根堆和小根堆恨闪，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值放坏，即A[PARENT[i]] >= A[i]咙咽。在數(shù)組的非降序排序中，需要使用的就是大根堆淤年，因?yàn)楦鶕?jù)大根堆的要求可知钧敞，最大的值一定在堆頂。
堆排序的介紹寫的比較好的文章是圖解排序算法之堆排序
#include <stdio.h>
void swap(int *a, int *b);
void adjustHeap(int param1,int j, int inNums[]);
void HeapSort(int nums, int inNums[]);
//大根堆進(jìn)行調(diào)整
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++;
}
//如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)溉苛，將子節(jié)點(diǎn)值賦給父節(jié)點(diǎn),并以新的子節(jié)點(diǎn)作為父節(jié)點(diǎn)（不用進(jìn)行交換）
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.構(gòu)建大頂堆
for (int i=nums/2-1;i>=0;i--)
{
//put the value in the final position
adjustHeap(i,nums,inNums);
}
//2.調(diào)整堆結(jié)構(gòu)+交換堆頂元素與末尾元素
for (int j=nums-1;j>0;j--)
{
//堆頂元素和末尾元素進(jìn)行交換
int temp=inNums[0];
inNums[0]=inNums[j];
inNums[j]=temp;
adjustHeap(0,j,inNums);//重新對(duì)堆進(jìn)行調(diào)整
}
}
int main() {
int data[] = {6,5,8,4,7,9,1,3,2};
int len = sizeof(data) / sizeof(int);
HeapSort(len,data);
return 0;
}
堆排序時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)弄诲。它是不穩(wěn)定的排序方法愚战。
歸并排序
用到了分而治之的思想娇唯，非常厲害的排序算法，很有必要理解寂玲，在一些Leetcode中的題目中會(huì)有用到相似的算法塔插。
參考文章：[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];//在排序前，先建好一個(gè)長(zhǎng)度等于原數(shù)組長(zhǎng)度的臨時(shí)數(shù)組拓哟，避免遞歸中頻繁開辟空間
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);//將兩個(gè)有序子數(shù)組合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指針
int j = mid+1;//右序列指針
int t = 0;//臨時(shí)數(shù)組指針
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//將左邊剩余元素填充進(jìn)temp中
temp[t++] = arr[i++];
}
while(j<=right){//將右序列剩余元素填充進(jìn)temp中
temp[t++] = arr[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數(shù)組中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
