当前位置：首页 > news >正文

常用排序算法实现

news 来源：原创 2024/5/20 3:02:45

时间复杂度

$O (1)$

void func1(int n){int count = 100;count++;
}
void func2(int n){int count = 100;for(int i = 0; i < count;i++){}
}
int func3(int n){return n;
}

$O (n)$

void func1(int n){int count = 100;for(int i = 0; i < n;i++){count++;}    
}

$O(n^2)$

void func1(int n){int count = 100;for(int i = 0; i < n;i++){for(int j = 0;j < n;j++){count++;}}    
}

$O (nm)$

void func1(int n,int m){int count = 100;for(int i = 0; i < n;i++){for(int j = 0;j < m;j++){count++;}}    
}

$O(\log n)$

void func1(int n){int i = 1;while(i < n){i *= 2;}  
}

$\log n)$

void func1(int n){int i = 1;for(j = 0; j < n; j++){while(i < n){i *= 2;}  }
}

空间复杂度

$O (1)$

void func1(int n){int a = 1;a++;int b = 2;b++;
}

$O (n)$

void func1(int n){int[] array = new int[n];for(int i = 0;i < n; i++){array[i] = i;}
}int sum(int n){int a;if(n == 0) return 0;return n + sum(n - 1);
}

$O(n^2)$

void func1(int n){int[,] array = new int[n,n];
}int sum(int n){int[] array = new int[n];if(n == 0) return 0;return n + sum(n - 1);
}

稳定性和冒泡排序

稳定性：当需要排序的序列中存在相同关键字的元素，排序后的相对次序保持不变，则算法稳定，稳定的排序算法会保留数值项顺序的表达意义。
冒泡排序：

int [] array = new int[]{2,5,6,7,1,3}
void bubbleSort(int[] arr, int n){int temp;int i,j;for(i = 0;i< n - 1; i++){for(j = 0; j < n-1-i; j++){if(arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

时间复杂度为 $O(n^2)$ ，空间复杂度 $O (1)$

改进版：

int [] array = new int[]{2,5,6,7,1,3}
void bubbleSort(int[] arr, int n){int temp;int i,j;bool flag = false;   for(i = 0;i< n - 1; i++){for(j = 0; j < n-1-i; j++){flag = false;if(arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true;}}if(!flag){break;}}
}

选择排序


void arr_sort(int *p,int n)
{int i,j;int min = 0;for(i = 0;i < n - 1;i++)//排序次数{min = i;for(j = i + 1;j < n;j++){if(p[j] < p[min]){min = j;//记录交换的元素下标值}}if(i != min){int temp = p[i];p[i] = p[min];p[min] = temp;}  }
}

插入排序

int [] array = new int[]{2,5,6,7,1,3}
void printArray(int[] arr){ls = "";foreach(var r in arr){ls += r + ",";}Debug.Log("轮次" + index++ + "数组" + ls);
}
void insertSort(int[] arr, int n){for(i = 0;i< n; i++){for(j = i; j > 0 && arr[j-1] > arr[j]; j--){int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}printArray(arr);}
}

时间复杂度为 $O(n^2)$ ，空间复杂度 $O (1)$

希尔排序

希尔排序是对插入排序的优化。

int [] array = new int[]{2,5,6,7,1,3}
void printArray(int[] arr){ls = "";foreach(var r in arr){ls += r + ",";}Debug.Log("轮次" + index++ + "数组" + ls);
}
void shellSort(int[] arr, int n){int i = 0;int j = 0;int temp;for(int step = n / 2; step > 0; step = step / 2){for(i = step; i < n; i++){temp = arr[i];for(j = i; j >= step && temp < arr[j - step]; j -= step){arr[j] = arr[j - step];}           arr[j] = temp;}printArray(arr);}
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O (1)$ ，稳定性是不稳定的

堆排序

堆是一颗完全的二叉树，堆中某个节点的值总是不大于（大顶堆）或不小于（小顶堆）其父节点的值

void heapSort(int[] list){// 构建初始堆for(int i = list.Length / 2 - 1; i >= 0; i--){AdjustHeap(list,i,list.Length);                // O(n)}// 进行n-1次循环，完成排序for(int i = list.Length - 1; i > 0; i--){         // O(nlogn)// 交换堆顶（最大数）到最后，并把这个节点从二叉树去掉int temp = list[i];list[i] = list[0];list[0] = temp;// 只有堆顶不确定是不是最大，只调整堆顶即可AdjustHeap(list, 0, i);}
}
public void AdjustHeap(int[] array,int parent ,int Length){int temp = array[parent];    // 父节点int child = 2 * parent + 1;  // 左子节点while(child < Length){// 找最大的子节点if(child + 1 < Length && array[child] < array[child + 1]){child++;}if(temp >= array[child])break;// 如果子节点较大，交换父子节点array[parent] = array[child];// 子节点作为父节点，进行下一轮比较parent = child;child = 2 * child + 1;}array[parent] = temp;
}

时间复杂度 $O(n\log n)$ ，空间复杂度 $O (1)$ ，稳定性是不稳定的

二叉树排序

二叉排序树：空树或满足以下条件

如果左子树不空，左子树上的所有节点值均小于根节点的值。如果右子树不空，右子树上的所有节点均大于根节点的值。
左、右子树分别为二叉排序树。
遍历顺序：
中序遍历（左根右）、先序遍历（根左右）、后序遍历（左右根）
我们采用中序遍历，也就是说，二叉排序树从小到大的遍历顺序是从最后最左的子节点开始，往上遍历，遍历到父节点的时候，再从下往上，从左往右遍历右子节点，如此往复，遍历完左右节点。

public class BinarySortTreeNode{public int Key{get;set;}public  BinarySortTreeNode Left{get;set;}public BinarySortTreeNode Right{get;set;}public BinarySortTreeNode(int key){Key = key;}public void Insert(int key){var tree = new BinarySortTreeNode(key);if(tree.Key <= Key){if(Left == null){Left = tree;}else{Left.Insert(key);}else{if(Right == null){Right = tree;}else{Right.Insert(key);}}}}// 遍历方法（妙啊）public void InorderTraversal(){Left?.InorderTraversal();Debug.Log(Key);Right?.InorderTraversal();}
}public static void BinaryTreeSort(int[] array){var binarySortTreeNode = new BinarySortTreeNode(array[0]);for(int i = 1; i < array.Length; i++){binarySortTreeNode.Insert(array[i]);        }binarySortTreeNode.InorderTraversal();
}

时间复杂度 $O(n\log n)$ ，空间复杂度 $O (n)$ ，稳定性是不稳定的

快速排序

参考：https://blog.csdn.net/qq_40941722/article/details/94396010

void Quick_Sort(int *arr, int begin, int end){if(begin > end)return;int tmp = arr[begin];int i = begin;int j = end;while(i != j){while(arr[j] >= tmp && j > i)j--;while(arr[i] <= tmp && j > i)i++;if(j > i){int t = arr[i];arr[i] = arr[j];arr[j] = t;}}arr[begin] = arr[i];arr[i] = tmp;Quick_Sort(arr, begin, i-1);Quick_Sort(arr, i+1, end);
}

function Sort(list, leftIndex, rightIndex)if(leftInfex >= rightIndex) thenreturnendlocal i = leftIndexlocal j = rightIndexlocal baseValue = list[leftIndex]while i < j dowhile i < j and list[j] >= baseValue doj = j - 1endwhile i < j and list[i] <= baseValue doi = i + 1endif j > i thent = list[i];list[i] = list[j];list[j] = t;endendlist[leftIndex] = list[i];list[i] = baseValue;Quick_Sort(list, leftIndex, i-1);Quick_Sort(list, i+1, rightIndex);
end

快速排序最优时间复杂度为O(nlogn)，不稳定

归并排序

参考：https://www.bilibili.com/video/BV1Pt4y197VZ/

function sort(arr, startIndex = 0, endIndex = arr.length - 1) {// 递归结束条件：startIndex大于等于endIndex的时候if (startIndex >= endIndex) {return;}// 折半递归let midIndex = parseInt((startIndex + endIndex) / 2);sort(arr, startIndex, midIndex);sort(arr, midIndex + 1, endIndex);// 将两个有序的小数组，合并成一个大数组merge(arr, startIndex, midIndex, endIndex);
}function merge(arr, startIndex, midIndex, endIndex) {// 新建一个大数组let tempArr = [];let p1 = startIndex;let p2 = midIndex + 1;let p = 0;// 比较两个有序小数组的元素，依次放入大数组中while (p1 <= midIndex && p2 <= endIndex) {if (arr[p1] <= arr[p2]) {tempArr[p++] = arr[p1++];} else {tempArr[p++] = arr[p2++];}}// 右侧小数组已排序完毕，左侧小数组还有剩余，将左侧小数组元素依次放入大数组尾部while (p1 <= midIndex) {tempArr[p++] = arr[p1++];}// 左侧小数组已排序完毕，右侧小数组还有剩余，将右侧小数组元素依次放入大数组尾部while (p2 <= endIndex) {tempArr[p++] = arr[p2++];}for (let i = 0; i < tempArr.length; i++) {arr[i + startIndex] = tempArr[i];}
}let arr = [4, 5, 8, 1, 7, 2, 6, 3];
sort(arr);
console.log(arr);

时间复杂度是O(nlogn)，稳定

排序算法的使用场景

游戏中得分排行榜
英雄战力榜列表等

拓扑排序

拓扑排序（Topological Sorting）是一种对有向无环图（Directed Acyclic Graph, DAG）进行排序的算法。在拓扑排序中，节点表示图中的任务或事件，有向边表示任务间的依赖关系。
拓扑排序的目标是将图中的节点按照一定的顺序线性排列，使得所有的依赖关系都得到满足。也就是说，在排序结果中，若存在一条从节点 A 到节点 B 的有向边，那么节点 A 在排序中必须出现在节点 B 之前。
通俗讲解：当同时存在很多件事情需要完成，但是有些事情的完成依赖于另外若干件事情的完成，拓扑排序需要我们排列出事情完成的顺序，这个顺序往往不止一种。

拓扑排序的算法通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。在实际应用中，如果图中存在环路（即有向图中存在回路），则无法进行拓扑排序，因为无法满足所有的依赖关系。因此，拓扑排序算法通常要求应用于有向无环图。

步骤

构建图：根据给定的有向图的边关系，构建表示图的数据结构。通常使用邻接表或邻接矩阵表示图。
统计节点入度：对于每个节点，统计它的入度（即指向该节点的边的数量）。可以通过遍历图的边关系，记录每个节点的入度。
初始化队列：创建一个队列（可以使用队列数据结构），用于存储入度为0的节点。
入度为0的节点入队：遍历所有节点，将入度为0的节点加入队列。
拓扑排序：从队列中取出一个节点，输出该节点（或保存到结果序列中），并将其相邻节点的入度减1。若某个节点的入度减为0，则将其加入队列。
重复步骤5，直到队列为空。如果输出的节点数量与图中的节点数量相同，则拓扑排序成功；否则，图中存在环路，无法进行拓扑排序。
输出结果：按照拓扑排序的顺序输出节点，即为拓扑排序的结果。

int topological_sort(LGraph G)
{int i,j;int index = 0;int head = 0;           // 辅助队列的头int rear = 0;           // 辅助队列的尾int *queue;             // 辅组队列int *ins;               // 入度数组char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。int num = G.vexnum;ENode *node;ins  = (int *)malloc(num*sizeof(int));  // 入度数组tops = (char *)malloc(num*sizeof(char));// 拓扑排序结果数组queue = (int *)malloc(num*sizeof(int)); // 辅助队列assert(ins!=NULL && tops!=NULL && queue!=NULL);memset(ins, 0, num*sizeof(int));memset(tops, 0, num*sizeof(char));memset(queue, 0, num*sizeof(int));// 统计每个顶点的入度数for(i = 0; i < num; i++){node = G.vexs[i].first_edge;while (node != NULL){ins[node->ivex]++;node = node->next_edge;}}// 将所有入度为0的顶点入队列for(i = 0; i < num; i ++)if(ins[i] == 0)queue[rear++] = i;          // 入队列while (head != rear)                // 队列非空{j = queue[head++];              // 出队列。j是顶点的序号tops[index++] = G.vexs[j].data; // 将该顶点添加到tops中，tops是排序结果node = G.vexs[j].first_edge;    // 获取以该顶点为起点的出边队列// 将与"node"关联的节点的入度减1；// 若减1之后，该节点的入度为0；则将该节点添加到队列中。while(node != NULL){// 将节点(序号为node->ivex)的入度减1。ins[node->ivex]--;// 若节点的入度为0，则将其"入队列"if( ins[node->ivex] == 0)queue[rear++] = node->ivex;  // 入队列node = node->next_edge;}}if(index != G.vexnum){printf("Graph has a cycle\n");free(queue);free(ins);free(tops);return 1;}// 打印拓扑排序结果printf("== TopSort: ");for(i = 0; i < num; i ++)printf("%c ", tops[i]);printf("\n");free(queue);free(ins);free(tops);return 0;
}

其中G是有向图，结构可能如下：

struct ENode
{int ivex;                   // 该边所指向的顶点的位置struct ENode *next_edge;    // 指向下一条弧的指针
} ;struct VNode
{char data;                  // 顶点的数据ENode *first_edge;          // 指向第一条依附该顶点的边的指针
} ;struct struct
{VNode vexs[MAX_VERTEX_NUM]; // 顶点数组int vexnum;                 // 顶点数量int edgenum;                // 边数量
} ;