# 数据结构与算法

**Repository Path**: zhang-wangbin/data-structure-and-algorithms

## Basic Information

- **Project Name**: 数据结构与算法
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-10-29
- **Last Updated**: 2024-10-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法

 
 
 

---

<!-- ## 绪论

&nbsp;
&nbsp;
&nbsp;

---

## 顺序表

&nbsp;
&nbsp;
&nbsp;

---

## 链表

&nbsp;
&nbsp;
&nbsp;

---

## 栈与队列

&nbsp;
&nbsp;
&nbsp;

---

## 串

&nbsp;
&nbsp;
&nbsp;

---

## 树与并查集

&nbsp;
&nbsp;
&nbsp;

---

## 图

&nbsp;
&nbsp;
&nbsp;

--- -->

## 查找算法

### 1. [顺序查找]()


&nbsp;
&nbsp;
&nbsp;

--- 

## 排序算法

- 十种常见的排序算法可以分为两大类：
  > **非线性时间比较排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(n·log(n))，因此称为非线性时间比较类排序。
  >
  > **线性时间非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

![](image/sort/sort_detail.png)

- 各类排序的时间复杂度：

![](image/sort/time_complexity.png)
<br/>

### 1. [冒泡排序](./content/9.Sort/1_Bubble_Sort.c)

> 嵌套 for 循环实现冒泡排序，每次循环确定最大 / 最小的元素，将其排至末尾 / 开头
>
> 每次循环对相邻两位的元素进行比较
>
> 复杂度：O(n^2^)

- 流程

![img](image/sort/bubble_sort.gif)

- 代码实现：

```c
// 冒泡排序
void bubble_sort(int arr[], int n,int flag){
	int i,j; // C语言得把变量定义在for语句外面
    for(i=0; i<n-1; i++){
		for(j=0; j<n-i-1; j++){
			if(asc_or_desc(arr[j], arr[j+1], flag)){  // asc_or_desc()函数用于设置升序还是降序
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}
```

<br/>

### 2. [选择排序](content/9.Sort/2_Selection_Sort.c)

> 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
>
> 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
>
> 重复第二步，直到所有元素均排序完毕。
>
> 复杂度：O(n^2^)

- 流程：

![img](image/sort/selection_sort.gif)

- 代码实现：

```c
void selection_sort(int arr[],int n,int flag){
	int i,j,min; // C语言得把变量定义在for语句外面
    for(i=0; i<n-1; i++){
        min=i;
		for(j=i+1; j<n; j++){
			if(asc_or_desc(arr[min],arr[j],flag)){
                min = j;
            }
		}
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
	}
}
```

<br/>

### 3. [插入排序](content/9.Sort/3_Insertion_Sort.c)

> 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
>
> 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
>
> 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
>
> 复杂度：O(n^2^)

- 流程

![img](image/sort/insertion_sort.gif)

- 代码实现：

```c
// 插入排序
void insertion_sort(int arr[], int n,int flag){
	int i,j; // C语言得把变量定义在for语句外面
    for(i=1; i<n; i++){
        int temp=arr[i];
		for(j=i-1; j>=0; j--){
            if(asc_or_desc(arr[j],temp,flag)){
				arr[j+1] = arr[j];
                arr[j]=temp;
            }
		}
	}
}
```

<br/>

### 4. [希尔排序](content/9.Sort/4_ShellSort.c)

> 复杂度：O(n^1.3^)

- 流程

![img](image/sort/shell_sort.gif)

- 代码实现：

```c
void shell_sort(int arr[],int n,int flag){
    int i,j,m=n/2;
    while(m){
        for(i=m;i<n;i++){
            for(j=i-m;j>=0;j-=m){
                if(asc_or_desc(arr[i],arr[j],0)){
                    int temp=arr[j+m];
                    arr[j+m]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        m/=2;
    }
}
```

<br/>

### 5. [归并排序](content/9.Sort/5_Merge_Sort.c)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/>

<!-- ### 6. [快速排序](content/9.Sort/)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/> -->

<!-- ### 7. [堆排序](content/9.Sort/)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/> -->

<!-- ### 8. [计数排序](content/9.Sort/)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/> -->

<!-- ### 9. [桶排序](content/9.Sort/)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/> -->

<!-- ### 10. [基数排序](content/9.Sort/)

>
>
> 复杂度：

- 流程

![img](image/sort/.gif)

- 代码实现：

```c

```
<br/> -->

### [补充排序中使用的自定义函数](content/9.Sort/head/sort.h)

- asc_or_desc 函数：用于自定义升序还是降序排序

```c
int asc_or_desc(int n,int m,int flag){
    // flag=1/0 => 升序/倒序
    if(flag){
        return n>m;
    }else{
        return n<m;
    }
}
```

- Print 函数：用于格式化打印数组数据

```c
// 格式化输出
void Print(int arr[],int n){
    int i;
    for(i=0; i<n; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}
```