#59
排序算法
0 次阅读
排序
比较排序
冒泡排序
每次遍历到尾，两两进行比较，遍历到结尾会浮出一个最值，形似冒泡，数组若有n个元素，则冒n-1次泡，最终全部排完。O(n),O(n^2),O(n^2)
void Bubblesort(int arr[],int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
选择排序
从数组一端开始遍历，假设当前位置 ind 对应值为最小值，从下一位 ind+1 开始第二层遍历，如果在第二层遍历中找到比假设值更小的数，则交换，遍历过后能把最小的数换到 ind 的位置，整体过程上看，每趟遍历把剩下的最小值排起来，最终全部排完。O(n^2),O(n^2),O(n^2)
void SelectSort(int arr[],int n)
{
for(int i=0;i<n-1;i++)
{
int ind = i;//假设最小值的下标
for(int j=ind+1;j<n;j++)
{
if(arr[j] < arr[ind])
{
int temp = arr[ind];
arr[ind] = arr[j];
arr[j] = temp;
}
}
}
}
插入排序
将数据分为已排序和未排序两部分，每次取一个元素插入到已排序部分的正确位置。
O(n),O(n^2),O(n^2)
void InsertSort(int arr[],int n)
{
for(int i=1;i<n;i++)
{
int key=arr[i];
int j=i-1;
while(j>=0 && arr[j]>key)//前面有比它大的
{
arr[j+1]=arr[j];//全部往后排
j--;
}
arr[j+1]=key;
}
}
快速排序
通过选择一个“基准”元素，将数组分为两部分，然后递归地对两部分进行排序。从平均时间性能而言，快速排序最佳。
O(nlogn),O(nlogn),O(n^2)
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int Divide(int arr[],int low,int high)//high = n-1
{
int pivot = arr[low];
while(low<high)
{
while(low<high&&arr[high]>=pivot)
{
high--;
}
if(low<high)
{
swap(&arr[high],&arr[low]);
}
while(low<high&&arr[low]<=pivot)//上面交换后自然比pivot小，直接进入while而不用手动low++
{
low++;
}
if(low<high)
{
swap(&arr[low],&arr[high]);
}
}
return low;
}
void QuickSort(int arr[],int low,int high)
{
if(low<high)//别忘了递归终止条件
{
int ind = Divide(arr,low,high);//返回中值
QuickSort(arr,low,ind-1);//递归排序中指左右两部分
QuickSort(arr,ind+1,high);
}
}
归并排序
通过分治法将待排序序列分为两个子序列，递归排序后再合并两个已排序的子序列。
O(nlogn),O(nlogn),O(nlogn),开辟数组以空间换时间，不受数据初始情况的影响
void MergeSort(int arr[], int l, int r)
{
if (l < r)//递归终止条件
{
int mid = l + (r - l) / 2;
int n1 = mid - l + 1; // 左部分长度
int n2 = r - mid; // 右部分长度
int L[n1], R[n2];
//递归调用左右部分
MergeSort(arr,l,mid);
MergeSort(arr,mid+1,r);
// 赋值
for (int i = 0; i < n1; i++)
{
L[i] = arr[l + i];
}
for (int i = 0; i < n2; i++)
{
R[i] = arr[mid + i + 1];
}
//比较并合并
int 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++;
}
}
}
堆排序
通过将数据构建成一个堆结构（通常是二叉堆），然后不断取出堆顶元素，并调整堆。
O(n),O(nlogn),O(nlogn)
- 建堆
从最后一个非叶子节点（下标为 n/2-1 ）开始，倒着检查该节点是否是子树的根，如果不是就调整（与子树中最大值互换，如3号节点和7号节点，注意，如果7号节点还有子树，交换后还需递归判断交换后子树是否是堆）。
- 排序
将堆顶元素与堆底元素进行交换，使旧堆顶元素归位，再对新堆顶进行调整建堆
-
下标从0开始的堆代码
void buildHeap0(int arr[],int n,int top) { int largest=top; //base on zero int left=top*2+1; int right=top*2+2; if(left<n&&arr[left]>arr[largest]) { largest=left; } if(right<n&&arr[right]>arr[largest]) { largest=right; } if(largest!=top) { int temp=arr[largest]; arr[largest]=arr[top]; arr[top]=temp; //don't forget to adjust buildHeap0(arr,n,largest); } } void heapSort0(int arr[],int n) { for(int i=n/2-1;i>=0;i--) { buildHeap0(arr,n,i);//from bottom to top } for(int i=n-1;i>0;i--)//don't have to deal with the last one { int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; buildHeap0(arr,i,0);//i:隐藏换到底部的最大值 } } -
下标从1开始的
//最大堆 void buildHeap(int arr[],int n,int top) { int left=top*2; int right=top*2+1; int largest=top; if(left<=n&&arr[left-1]>arr[largest-1]) { largest=left; } if(right<=n&&arr[right-1]>arr[largest-1]) { largest=right; } if(top!=largest)//如果当前堆顶不是最大的 { int temp=arr[top-1]; arr[top-1]=arr[largest-1]; arr[largest-1]=temp; //别忘了交换后还要调整子树 buildHeap(arr,n,largest); } } void headSort(int arr[],int n) { for(int i=n/2;i>=1;i--) { buildHeap(arr,n,i);//从下到上构建堆 } for(int i=n;i>=2;i--) { int temp=arr[i-1]; arr[i-1]=arr[0]; arr[0]=temp; //调整堆 buildHeap(arr,i-1,1); } }
非比较排序
基数排序
按照元素的位数进行排序，每次排序时根据某一位数的值对数据进行排序，依次处理每一位。
O(d(n+rd)) , O(d(n+rd)) , O(d(n+rd))
分为最低位优先法（LSD）和最高位优先法（MSD）
第一趟排序（个位）：
桶排序
计数排序
其他排序
希尔排序（插入排序改进版）
O(n^3/2) — O(n^7/6)
Tim sort
排序算法性能一览
