算法与数据结构知识点及面试题总结（持续更新中）

1.经典排序复杂度分析及常考排序算法

经典常考排序算法：

1.归并排序

void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 

    int L[n1], R[n2]; 

    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        int m = l+(r-l)/2; 
  
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}

2.快速排序

#include<iostream>
using namespace std;
void quickSort(int a[], int m,int n);
int partion(int a[], int m, int n);
int main()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	int m = 0;
	int n = (sizeof(a) / 4)-1;
	quickSort(a, m,n);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
}
void quickSort(int a[], int l, int r)
{
	if (l < r)
	{
		int q = partion(a, l, r);
		quickSort(a, l, q - 1 );
		quickSort(a, q + 1, r);
	}
}
int partion(int a[], int begin, int end)
{
	int stone = a[begin];
	while (begin < end)
	{
		while (begin < end && a[end] > stone)
		{
			end--;
		}
		swap(a[begin], a[end]);
		while (begin < end && a[begin] <= stone)
		{
			begin++;
		}
		swap(a[begin], a[end]);
	}
	return begin;
}

3.冒泡排序

void bubbleSort(vector<int>& a)
{
      bool swapp = true;
      while(swapp){
        swapp = false;
        for (size_t i = 0; i < a.size()-1; i++) {
            if (a[i]>a[i+1] ){
                swap(a[i],a[i+1]);
                                /*a[i] += a[i+1];
                                a[i+1] = a[i] - a[i+1];
                                a[i] -=a[i+1];
                                */
                swapp = true;
            }
        }
    }
}

4.选择排序

void selectionSort(vector<int>& arr) {
    int len = arr.size();
    int minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        swap(arr[i], arr[minIndex]);
    }
    return;
}

2.判断链表是否有环

答：

    bool hasCycle(ListNode *head) {
        if(head == NULL) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }

3.当排序几十个数的时候用哪种，几十万个数的时候用哪种?

答：