JZTXT

排序详解

发布时间 2023-05-24 18:40:43作者: Gery_8002

排序

简单排序

插入排序

普 code

int n, cnt = 0;		 // 数组长度 插入数组长度 
int a[10005], r[10005];	 // 原数组 插入数组 

void InsertSort(int x) { // 插入 x 
  int pos = 0;	         // 记录 x 应插入的位置 
  
  while (pos < cnt && r[pos] < x) pos++;
        		 // 直到找到大于等于 x 的数 
  for (int i = cnt; i > pos; i--)
  	r[i] = r[i-1];
                         // 后移数组 
		
  r[pos] = x;
  cnt++;		 // 插入数组长度加一 
}

空间优化 code

int n;
int a[10005];

void InsertSort() {
 for (int i = 0; i < n; i++) {
 	int pos = 0, x = a[i];
	while (pos < i && a[pos] < a[i]) pos++;		
	for (int k = i; k > pos; k--)
	    a[k] = a[k-1];
	
	a[pos] = x;
   }
}

冒泡排序

普 code

void bubble_sort(int* a, int n) {
bool f = 1;
	
while (f) {
	bool f = 0;
	for (int i = 1; i < n; i++)
		if (a[i] > a[i+1]) swap(a[i], a[i+1]), f = 1;
  }
	
return ;
}

常数优化 code

int n;
int a[10005];

void BubbleSort(int n, int a[]) {
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n - i - 1; j++) {
		if (a[j] > a[j+1]) swap(a[j], a[j+1]);
	}
  }
}

选择排序

普 code

int n;
int a[10005];

void SelectSort(int n, int a[]) {
	for (int i = 0; i < n; i++) {
		int key = i;
		
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[key]) key = j;
			
		swap(a[i], a[key]);
	}
}

优化 code

int n;
int a[10005];

void SelectSort(int n, int a[]) {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[i]) swap(a[j], a[i]);
	}
}

复杂度

时间复杂度

插入排序

O (n ^ 2)

冒泡排序

O (n ^ 2)

选择排序

O (n ^ 2)

实用排序

归并排序

O (n log n)

code

int n;
int a[10005], t[10005];        // a 原数组 t 排序数组 

void MergeSort(int l, int r) {
	if (l == r - 1) return ;
	
	int mid = (l + r) >> 1;
	
	MergeSort(l, mid); MergeSort(mid, r);
	
	int p = l, q = mid, k = l;
	
	while (p < mid && q < r) {
		if (a[p] < a[q]) t[k++] = a[p++];
		else t[k++] = a[q++];
	}
	
	while (p < mid) t[k++] = a[p++]; // 复制剩余数组 
	while (q < r) t[k++] = a[q++];
	
	for (int i = l; i < r; i++)
		a[i] = t[i];
}

快速排序

O (n log n)

code

int n;
int a[10005], t[10005];

void QuickSort(int l, int r) {
	if (l >= r - 1) return ;
	
	int flag = a[rand() % (r - l) + l];
	int p = l, q = r;
	
	for (int i = l; i < r; i++) {
		if (a[i] < flag) t[p++] = a[i];
		else if (a[i] > flag) t[--q] = a[i];
	}
	
	for (int i = p; i < q; i++) // 复制剩下等于 flag 的数 
		t[i] = flag;
		
	for (int i = l; i < r; i++)
		a[i] = t[i];
		
	QuickSort(l, p);
	QuickSort(q, r);

特殊排序

字符串 sort 排序

In bool cmp(const string &a, const string &b) {
	return ((a + b) > (b + a));
}